Other than smart playlists, your requirements describe pretty much any media player released in god knows how long.

Personally I usually have an internet connection except on the train, so I use a Subsonic server, and my Android Subsonic client is set to aggressively precache my playlist (so it plays happily through tunnels, even if the tunnel lasts 10+ songs).