If it is already a crowded space with entrenched players, consider focusing on a niche area initially, instead of going head to head with the existing leaders of the space. This is probably what you would have done if there were no search engines, and it’s often still the best approach. Find something that the entrenched players do not do well, and focus on that. Establish a reputation in that niche, become a leader in it, and then expand from there.
One great example of this is hipmunk.com for travel. They offer great visualizations of what your trip is going to be like. It’s a fantastic UI, and it’s attracting the attention of a lot of people.
I'm feeling the love, sir. Thanks!