For me, the best music phones on the market are all made by Sony Ericsson. Check out the W810i
(512MB memory stick) and W950i
(4GB flash) for how to make a music phone.
The UI on their music phones is absolutely superb. Whether you want to listen to music or make a phone call, it's easy-to-use and responsive. They're also small and have classy looks. Not only that but the sound quality is actually very decent (better than the iPod) and they come bundled with quality headphones.
Pocket PC or Smartphone would give you the features, but would it give you an easy-to-use and responsive UI? Have you tried using WMP on a Windows Mobile phone? It's a pain in the ass.