I would like the search to be similar to that of iTunes. That being that a small DVD case would show what the movie is (these are easy to grab from Amazon, etc) or maybe by default, a random (or user chosen) Image would appear it this place that again could be replaced by the user.
I might be different from most people, but I pretty much would just need to search by title. The movies or video I have in my car is generally pretty straight forward, so searching by actor is not all that important. Genere might be nice.
As for which formats, I encode all my DVD's with Handbrake. So I prefer .mov, .mp4, and also (if possible) h.264.
I play most of my movies with QuickTime, but VLC has many advantages too.
Keep up the great work!