How do I overcome the Magento CMS editor reformatting my html (removing new lines)
I write down this

And after I save it looks like this

Note: I had revised my answer after some more investigations.
Although tinymce has hardly any code formatting capabilities (really, they are not something to go crazy over), it should not remove new lines.
Having had a look at magento 1.9 demo cms, I find it's formatting (for me in chrome) retains new lines. From http://www.tinymce.com/wiki.php/Configuration3x:remove_linebreaks this may be browser dependant.
Have you tried a different browser (chrome) to see if the same happens?
As previously stated: There are numerous modules available that replaces the default WYSIWYG with more modern ones. This would most likely be your best bet.
I do not have any personal experience with any of those, so cannot recommend a good one.
Maybe these settings can help in tinymce.iniu
remove_linebreaks : false, preformatted : true,