I used to use a route from Silly Oak to a friend's house in Erdington as a test of maps/routing. It's particularly challenging, because you've got to cross Birmingham, which means either horrible roads with Big Scary Roundabouts, or COR and taking your chances with the Aston ASBO Geese and Silly Sustrans Gates on the towpath. There isn't really a good answer (other than not to go to Erdington in the first place).
Google seems to give sensible towpath-based answers, but needs a lot of persuading to avoid them.
There was a time when my eTrex would crash attempting to find a route, presumably due to OSM glitches and lack of memory. It currently seems to favour a curious outer ring road route.
Cyclestreets manages to come up with more-or-less the road route I'd actually use (which involves very careful navigation of a Big Scary Roundabout so as not to end up on the Aston Expressway), and a route using NCN5 and the Grand Onion Canal which would be the one favoured by the experienced yet traffic averse Brummie cyclist.
Strava has a winning answer at the moment. It weights roads according to actual use by cyclists, which makes for a very powerful tool, as long as your preferences are in line with those of the average Strava user: There's a strong roadie/commuter bias, but that does make for reasonable on-road routes if you're not scared of traffic.
The sensible option is probably to take the train.