I'm sure this is an error, and a moronic one at that. Otherwise even safari infringes on Apple's rules. The real maddening thing is that there is no appeal process and no (mainstream) way to distribute your app if Apple has a vague problem with it. I hope for a day we will have mobile devices that are free and usable.
No, Safari doesn't have this problem. One remedy the OP was offered was to require the user to choose the third-party content to display. That's just what Safari does. (BTW, I don't think it's an appropriate remedy in this situation. I'm just saying this isn't inconsistent with Safari.)
There are probably links to websites that link to the wider Web too on the safari new tab page (though I haven't used a fresh safari in some time so I might be mistaken).