Don't know about the Delorme GPS but we have used Street Atlas 6,7 and just got Deluxe so can't comment on Deluxe. The Deluxe interface is extremely different than the regular SA so we'll need some experience with it to come to any reasonable conclusions.
However, on SA 6 and 7, my copilot uses the software on the road and has used it on her own. Though she isn't a master of it( I do the route planning mainly because computer stuff is my thing), says she'll never go back to paper maps.
You don't need routing if you want to use it just like a paper map at first with the advantage of always knowing exactly where you are on the map when used with a GPS. The rest of how to use the software comes with a experience.
At first it may seem complex. Once you get the hang of it, you wonder why you thought it was so hard.