"Horrendous!" "truly awful"? Can you elaborate on what exactly is wrong with OsmAnd's UI to elicit such a strong reaction? I use it myself and don't have any problems with it. It seems about the same as any mobile app with comparable complexity.
To search you press the menu, select search, select search by name (not the top item), get a box called "filter" with an almost invisible search button and where enter does not do a search. If it doesn't find any matches it just leaves a blank screen as if nothing has happened. Oh and if you pressed return first it wont find anything as the carriage return is part of the query so it doesn't match.
When I finally get the results of my query for "Hammersmith" it tells me that 309km away (some mistake, more like 3.9km) there is "Subway Station District Line;Hammersmith & City Line", and then the same result repeated around 150 times some with slightly different naming, and at varying distances from 309-328km away before it gets to other results in Hammersmith.
And you are trying to use this on a phone in the rain, you just give up and go back to google maps even though the data is worse.
EDIT: And if you select one of these it appears to be in Barking, as it found every station on the Hammersmith and City Line, although that is not 300km long.
Granted, I've never used it in a hurry. Also, my previous experience with maps was Garmin's City Navigator, which I thought was okay, but it was much worse than OsmAnd. I actually still use have it as a backup because it can run continuously for two days on two AA batteries.
The problem is expectations. When I pull up my map application, I want to find a position on it, usually navigate to it, and do so quickly. Having to navigate menus containing way too many unnecessary options slows me down and discourages most people from using it when gMaps has a simpler interface. Additionally, the maps seem very cluttered with useless information (for immediate navigation). Perhaps the best option would be to get rid of some of the features, since more features != better application. In the end though complexity isn't an excuse for a difficult interface.
The UI is not perfect, but it has lots of useful features, like bike navigation and offline usage.