Having shot both, and switching to Nikon after years of Canon use, here are a few thoughts.
1. Dynamic range on the Nikon is next to amazing, easy 2.5 stops and 3 at times. When pushed shadows at base iso are very clean. In fact up to around iso 400 this holds true. After 400 you will start to get diminished returns.
2. Lens line, not sure on that as to my both companies are pretty much the same.
3. AF. you are correct, the MKIII has a great AF, accurate tracking in AI servo mode and in deep deep shadows. The D800 will have trouble in the shadows. Not as bad as older Canon's I have used like the 1ds MKIII and 1ds MKII and 1D MKiv. If you are after action, especially moving action, the Canon has a definite edge.
4. High iso performance. I owned the MKIII for about 1 month, and never found the high iso performance that impressive. Others seem to. I found the same issues as with all other Canon bodies I have used, with higher iso, the increase in Canon Blue red noise increases and makes the file very hard to use. The only Canon I have tried without this is the 6D. The Nikon does get noisy past 3200 but it's a more grain like noise, and is easier to clean up.
5. Hand holding. I do it all the time. No problems just keep your shutter speed in check. I have had problems with Nikon VR and movement. I believe this is me not the tech. Nikon's VR and Canon's IS do react a bit differently.
6. Best advise. Rent them both, www.lensrentals.com
They have both bodies and you can try them out. Their rates are great. Shot them side by side and then make the call. I can assure you no two people will react the same as everyone has their own shooting styles and needs.
I made the painful decision to move to Nikon last year. Painful due to amount of glass and bodies I owned. I am a landscape, outdoor shooter and the DR of the Nikon was what made the call for me. It still impresses me with what you can get with a single frame. Looking back, I have no regrets, I don't feel Canon has yet to release anything with the DR of the D800. or D600. As I mentioned the 6D has some areas of impressive improvement but the AF is very basic.