I'm a fairly recent (~2 years) iPhone user too. I guess I've never actually browsed the App Store. I feel like I've always known the app I was looking for ahead of time, either because it was suggested to me or it was something I already knew about.

If it's that bad, I'd probably say your best App Store curator will probably be Google. Try just Googling "iOS local music player" and see what you get! For me, I got some article listing the top ten iPhone music apps...
_________________________
Matt