Well I got a Nokia 6233 not too long ago. I mostly just wanted a cheap phone that could play MP3s, but it turned out to support a lot of other neat things too, such as e-mail, videos and Java applications. This basically means that you can use cool stuff like Opera Mini (or other HTTP browsers), FTP browsers like Moby (though I haven't tried it yet) as well as other neat applications such as Telnet clients and multi-protocol messaging programs and also online games like Tibia Micro Edition (which is really shitty but still).
You can also pirate commercial mobile games and transfer them to the phone via Bluetooth or some kind of adapter I guess, or just get free applications and games from sites like GetJar which has tons of freeware and ad-supported stuff.
I need to point out the fact pretty much every phone in the market nowadays comes with Java.
Features you might want include:
-Bluetooth (Stereo if you plan on using it for music, I've heard the quality of bluetooth stereo ain't too great, however...)
-Expandable or large memory (Again if you want music, or maybe just photos or a lot of applications or whatever)
-Some kind of actual music player.
-Synchronization with pcs.
-I am very dumb today and can't really think of useful stuff.