Songs are dead simple to find.
I have somewhere around 4500 songs loaded on my iPod, sure it's not 15000, but:
Music -> Playlists
-> Artists
-> Albums
-> Compilations
-> Songs
-> Genres
-> Composers
Pick one, and you can drill down further, you know the artist? Perfect. The album? Works too. Even flipping through all 4500 songs doesn't take all that many spins of the wheel.
Besides, how often are you looking for just that one song? I listen to trance when I code, selecting the trance genre, and turning the shuffle on is *perfect* for me.
The interface is not just easy - it's intuitive enough that once I showed my 7 year old daughter the iPod and explained what it was for, and showed her how to roll her finger around on the wheel, that she was navigating it. Literally 20 seconds and she was flipping through the songs.