Searching within the titles, not just from the beginning (that gets rid, among others, of 'The' problem, first/last name problem etc).

It already skips the "The" automatically, as well as foreign variants such as "La". (That really impressed me when I noticed it.). So, for "The Pretenders", you can safely start with "P", for example. But for "Paula Cole" you can't start with "C", you have spell the first name, too.

I think there's a good reason it doesn't do a full substring-search: If it did, you'd get too many search hits and you'd have to press too many letters to get to what you wanted. As it stands right now, you can usually find the title or artist you're looking for with three or four letters. If they made it a substring search, it'd be more like 6-10 letters. Since this is meant to be used in the car, they have to make it as few keystrokes as possible.

As for the other things you mentioned, those have all been brought up elsewhere in the wish list forum, and I agree that they would all make good additions.

___________
Tony Fabris