Identifying patents and then following a course of action

I am developing a piece of software which I believe is really cool and very useful. I am currently primarily targeting Android, but I would like to target iOS, Windows Phone, and Windows RT in the future as well.

The problem: there is another company that has developed a program very similar to what I am developing, and their program has been around for about 25 years now.

The catch: this company's program does not exist on mobile devices, and so, in a sense, I would like to provide some competition in the mobile device sector of the market.

The question: Is there an easy way to do a patent search that will return a comprehensive, readable list of patents? I know the US Patent Office's website has a patent search tool, but it is quite archaic. Even Google's doesn't really do what I'd like it to do. (Google Patents seems much more primitive than Google Scholar).

I am still several months away from releasing the app that I am building, but my progress is coming along substantially, and I would like to know what patents I could run into before continuing my development. Although I don't agree with software patents by principle, I would like to respect the patents that exist to try and avoid any legal troubles if I release this app and this company tries to take any action against me.

I would say if you are really serious about it, then your best bet might be to hire a patent lawyer. I'm sure there is a DIY way to find the patents that may be pertinent, but frankly... patents can be quite vague. It's entirely possible that you wouldn't consider a patent to be relevant until you fully read and comprehend the details of it. There are professionals that do this work for you... they aren't cheap, but if patent infringement is a genuine risk, then they'll be worth it in the long run.

If the other program has been in the market for 25 years - well, patents only last 20. So any patents that protect the old program should in theory be expired or about to expire.

Of course, the US patent system being what it is, there's always something you can get sued over, and it's basically impossible to find all the patents that might or might not pertain to what you're doing.