How do you normally structure your Menus?
One option you have is to leave your menus as they are and use CSS to style the page so it appears nicer.

You can do things like reduce the amount of space between menus.

Another way (this depends on your sites menu requirements - it may not fit with what you need), is to have primary links be your sitemap.
Add everything you want in your site map to the primary links, going in as many levels deep as you need.
Then don't actually display all the levels in your menu (unless you want to and have deep drop down menus).
Then have the site map just display the primary links menu.

This will give you a nicer looking site map.

In my opinion, site maps are something drupal does not do well (short of doing something more custom). I have never seen a satisfactory result (to my standards) from using the site_map module.

Another option would be to use the menu_block module, which would allow you to create a bunch of menu blocks for specific menus (and levels of those menus), which you could then position on your site map page in a grid (or whatever layout you prefer).
This allows you to be very specific with what is displayed on the sitemap and how it is displayed.
Menu blocks also means you can customise the heading specifically for that block, without changing the name of the menu.
You could assign the blocks to a node page that has some introduction text for the body, of you could use something like the empty_page module to add a non-node sitemap page to assign your blocks to.

You can call your menus whatever you prefer, but I would not rename them to primary and secondary links. It is better to use more semantic names.
This is important in cases where you want the menu title displayed with the menu, and also when the menu title is there but hidden, to give screen readers better context, for accessibility.

Whether or not to display the manu titles in the site map also depends on your site setup and what you want to achieve.
If your menus are for distinct sections of the site it might be useful to have those sections stated in the sitemap, however if the title is not really relevant, for example "Main manu", "Navigation", "Footer links" etc., then it would likely be best to not show them.