I don't like VLC, that works not good. On PC I used Winamp for a long time, but it became very strange. So I moved to the foobar2000, it's a simple player, but works well.
On phone I have very cool apk, I downloaded it here http://theappsdepot.com/
It's called easy - Music Player. It has the useful feature that I like - give your phone a shake to play the next or previous song.