I'd probably recommend an iPhone, if you want an unused phone and aren't tied to a slimmer budget. Partly because they are more reliable for a complete smartphone newbie, but also because of the greater second hand value over Android phones. If you end up not liking iPhones, it will probably be because you think they're a bit boring and want to be able to customize more/have more control over the functionality of the phone. In that case you can easily sell your iPhone at a good price and get an Android instead. The reverse would cost you more, especially after 6 months or longer.
Personally I love Android as well though and if you're not completely averse to doing a bit of setting up on your own, I'd definitely check out some of those phones.
One thing though, and I am speaking from experience here: When you test Android phones in a store - don't be too put off if even a brand new "flagship" phone is completely lagged down or has a terribly ugly UI. I don't know quite what happens to these poor phones in stores, but they're generally not set up very well because people fiddle around with settings and stuff on them all day long, and they eventually get competely messed up. And the UI you will be able to mostly re-design to your own liking.
I checked out the Note 2 for 6 months before eventually buying one, and time and time again I would be put off by how ugly TouchWiz looked and how extremely laggy the phone would be in some stores. When I finally decided to make the leap though - it was awesome. Ultra fast and with the UI of my choice, icons, haptic feedback, homescreen, gestures - everything. Because then I finally had the chance to set one up properly.