I seem to recall I had a windows phone at the time, with a full keyboard. I could use OS maps on the thing, and although it didn't have GPS, it could get my rough location by tower.
My mate had an iPhone, and it had an app where you could pretend to drink a pint of beer.
That might prove the novelty of the App Store back then. Also, let’s not forget that its’ screen was better than most other smartphones of its time. It was a rather limited phone, but not bad exactly.