I use two different solutions for this. First is a program called Gesture Search. It works with the standard search database and lets you search by using your finger to write the letters you're searching for on the screen. Very slick. But, like the dumb default People app, it only searches names.
So I also use Better Contacts, which searches names and company name, which I like. It also searches SMS, web, calendar, and more, which can be good or bad, depending on what you want to do.
One thing you can do in People, which makes it better, is do a two finger scroll. This scrolls down one alphabet letter at a time, so you can get from the A's to the M's very quckly. And a two finger tap at the bottom of the screen jumps to the end of the list, a two finger tap at the top jumps to the top of the list.