3G smartphones (mostly Nokia N60 platform) were a thing from about 2002 in some European markets, with rather limited uptake. The real killer feature of the iPhone, at least initially (remember the first one didn't have 3G in any case) was a browser that didn't make you want to throw the thing out the window in frustration every time you used it.

The iPhone was pleasant to use, or at least not actively infuriating. That was, to a large extent, all it took.

Nokia really messed up, here; there was nothing stopping them making an iPhone-ish thing (perhaps without multitouch) a few years previous to the iPhone coming out, and there was even a semi-decent third party browser for their platform (Opera) which they could have taken cues from or bought, but they were always far more excited about the featurephone market, seeing smartphones as a niche.