Yeah, difficult one I think.
I for one hate adds in any form on any media - with a passion.
To me, a fairly good game free of adds, is way more professional than an excellent game with adds.
Actually I refuse to put adds in my games - and it would be a fantastic thing if every dev - large or small, pro or indie - would do the same thing.
But to the concluding question of your post:
Paid up front:
Likely lead to less downloads. (It seams these days people don't even want to spend .99!) At least until you get a name for good products.
Implement Adds:
Most annoying thing on the planet. Only do it if the paid version removes the wretched things completely. (hmm nah, what am I saying, dont' do it at all..!!!)
Other options:
First level free:
Up grade to unlock all levels.
Completely free:
In-app purchases for more powers, weapons, vehicles etc. But be careful, don't make it seem like a money pit, and make the purchase really special.
Just my 2 cents worth, I am sure others will see things differently....