This is all possible, I think the easiest way is to hire a DNN skinner... Or you will have to read the skinning documentation and learn your self (link is in the top post of this Forum)

I know exactly how you can solve these problems ... hire me!  .

Breadcrumbs is easy its a configurable control... so you can change the level its looking at.

Legacy + various attempts to make default providers as generic as possible have made navigation a 'can of worms'.   There is an 'open' navigation provider plugin capability within dotnetnuke and a number of commercial navigation providers... 

I've even writen one of my own 100% css based XHTML accessable etc ... see in action here http://www.clicproducts.no/Home/tabid/36/Default.aspx 

The same situation is true for sitemaps (although a LOT simpler to construct than an all singing all dancing menu).

As with all things DNN the default setup will do a hell of a lot, but to get what demanding clients actualy want and need you have to customise, luckily the achitecture is rather good so if you know what you are doing with ASP you can take it as far as you need to.

As for least effort... buy a provider there are some very good ones these days... I'd tell you how to do it but seriously you would have to be psychotic or stupid to want to attempt it when you can spend 100 bucks and do something else with your time.