I like the look of this new feature—I think it will be more useful to beginning users, it produces a nicer first-run user experience, and it gets out of the way very quickly.
I'm not sure if people think that Google Chrome has ads like this or not—to my view, the whole product is laced with ads for Google products, far more intrusive, obnoxious and anticompetitive than anything Firefox has been able to produce.
(You might guess that I'm a Mozilla fan. That perception would be accurate.)
I personally take objection to ads when they take away from the usability of the product, when they are of a form that could be used to infect my computer, and/or when they are of a form that can be used to pass on data to third parties. (Un?)fortunately, this covers the majority of advertisements on websites: a large chunk of ads are pop-up, pop-over, are flash (both for battery life and exploits), redirect to untrusted websites (exploits), and/or use content hosted by third parties.
As such, my worry for this is: what happens if someone buys a spot that takes you to a page that exploits your computer then redirects to (for example) facebook? I hope that the bar (price for a spot) will be high enough to discourage this, but I don't know...
That being said, I think the proposed ads are very tasteful, and it won't affect my browser use.
I also won't argue your point about calling the pre-installed search engines as ads--but they have a utility to them. The upcoming ads are going to have a hit or miss utility. Either I frequent that sponsored site, or I don't and find it to be a waste of space on my new tab page until it gets filled out by another site.
I think if anything, I'd just be worried that this is a slippery slope for Mozilla. These new sponsored site listings seem completely un-intrusive for now... but could it go further in the future?