My first smartphone was the Nokia 7610 that was gifted to me sometime in 2004.
It had a 176x208 screen with support for 65K colours. It had 8 MB RAM and 64 MB of storage.
It ran on Symbian Series 60 2nd Edition. I don’t think there was an app store. I remember getting J2ME apps/games off of third party stores. Note the presence of RealPlayer:
In terms of applications, I had a J2ME version of Google Maps, which was very impressive in 2004; this was when paper maps were still commonly used. The J2ME version of Gmail also felt very futuristic.
It had a browser that could access the regular web (not just WAP). Vast majority of websites had no mobile friendly views, but websites were somewhat simpler then. Google Search did have a good mobile web version as did Google News (if I remember correctly). Keypad navigation actually worked much better than you think it would.
I did listen to MP3s on the Nokia 7610, but you could only put a few on the phone. You technically could also watch videos, but I never tried it.
I believe I kept using this phone all the way till 2007-2008 when I switched to another Symbian device. I only switched to Android with 4.x when I got the HTC One X in 2012.
I remember running some J2ME-stuff on the Sony Ericsson-phones, but it was generally quite incapable. Maybe it was a lack of creativity on my part, but then again, I was in my teens at this point