You were pretty much on the right track with what you said. When you go to "shodan.io" it uses HTTP. The firewall can do a "man in the middle attack" on this HTTP session and present the URL block page.
On the Google Search result for shodan.io, the URL is https://. Without SSL decryption, the firewall cannot do a MiTM attack on the SSL site to present the block page, however access to the site can still be blocked as per your URL filtering configuration.
To conclude, if you want to present block pages for SSL sites - you will need to configure SSL decryption.