I think they need more cool features for people to say that they are really impressed with the new phone. But they don't need to iterate more than they have been to keep people buying them.
Apple had its paradigm shift with the phone. You can't just have those every year. Outside of the initial introduction of the iPhone, and then allowing apps, it's really just iterating, and I don't see how one could expect much different. Their competitors certainly aren't shifting any paradigms with their competing offerings. I think the biggest splash Apple (or others) will be able to get for a bit will have to come from a stylistic redesign (Lumina got many nods for this). Outside of that, it's just the march of the features, apps, and ecosystem.
On paper, the S III has a larger screen, NFC, a slightly higher MP front-facing camera, a barometer, and access to more Google services, like Maps, Play Store and Now (assuming the majority of Galaxy S III owners ever upgrade to Android 4.1).
For me, personally, none of those are remotely compelling. But then I'm heavily tied to Apple's services and love the App Store, so I'm quite biased.
Regarding hardware, aside from new enclosures, I don't expect any major changes in the near term. I doubt they'll add NFC any time soon, if ever. Why bother? The 4S and 5 support Bluetooth 4, which offers many NFC like features, and there's no compelling reason to add explicit NFC support now or anytime soon. Likewise, I bet it'll be a while before induction charging makes an appearance – again, if it ever does. Induction charging just adds bulk and isn't a huge step forward for most users; placing your phone on a charging pad is effectively equivalent to docking it.
The "cool new features" will probably continue coming from software, just as has been happening with Macs. Most Macs are only evolutionary improvements over their predecessors, with the occasional enclosure redesign. That hasn't harmed Mac sales in the least.
In order for Apple to maintain its unprecedented brand recognition and profit margins it's not good enough to match the competition. They have to be unambiguously better than the Android alternatives and they just aren't right now.
I disagree… are Macs unambiguously better than the alternatives? I'd say they aren't, but they still give Apple unprecedented brand recognition and profit margins. Ditto for iPods. For years, Macs and iPods often only saw incremental and obvious improvement.
Innovations don't always need to come from Apple; as is eagerly pointed out here, Apple's quite happy to let others pioneer tech (like, say, NFC) and only adopt it when it makes sense for Apple's product story.
Apple creates a superior story, a superior experience. That's it. Macs, iTunes, iPods, Apple Stores, and iOS devices all play together to offer clear and obvious benefits to consumers. Apple only needs to innovate when nothing currently on the market meets their product goals. Otherwise, they're focused on improving and refining the tech they're already shipping.
iPhone simply feels outdated because it's not as "online" as Androids are. The notion of "syncing" reminds me of my decade-old Nokia, the maps are barely useful (I use google maps via browser instead), the address book, the mail app, the way you use it is just ughh... old school: everything lives on an island which needs to be "synced". You can't even put a music on it without the iTunes, still. And even basic UX is plain wrong in many places, for example why does it keep beeping when receiving SMS messages while I'm typing??? Sorry, but this is a phone from 5 years ago. The world has moved on.
Personally, iCloud solves all of my syncing issues; the device is basically always online and all of my data's always up to date without manually syncing. All of my media is in iCloud, so I never need to sync my music, movies or TV shows. Likewise, I can purchase all of that media from the iTunes store on the device. Maps on iOS 6 is hugely improved with an enormous (and potentially disastrous) regression – there are no transit directions. And I've never noticed the beeps from Messages when I'm typing a response… I must have internalized and learned to ignore those. ;-)
I think it may really come down to: I can't use Android because I'm so tied to iCloud/iTunes and some of my favorite apps (Tweetbot and Reeder are probably the big ones) haven't been ported to Android. Also, the lack of polish on Android (even in 4.1) and in all Android apps drives me nuts. Maybe I'm too brainwashed by iOS. Every time I use an Android device, I feel like I've picked up an unusable and barely functional rip-off of iOS.
Likewise, perhaps iOS isn't usable to you because you're so tied to Google's ecosystem, and you're accustomed to Android and Android apps. And because you're used to the way everything works in that universe, iOS feels like the backwards, decrepit OS.