On windows, or Mac/Linux, you can use ffmpeg or avconv with the video filter option -vf "transpose=1" (you many need to either use a different number or use it more than once to get the results that you need).
Both are free (libre & FOSS) utilities/libraries that, as well as being able to convert between 100s of video storage formats, allow a large number of other operations to be performed on the files including transposing the video.
The amount of quality loss depends largely on the codec used in the input, (and output), file(s). You can also control the quality by changing the bit rate, changing the resolution, etc., so as to reduce the file size. One example is to create HD, Std & Mobile versions of the same video but you will never really get a higher resolution or quality than your input file(s).
While ffmpeg and its later fork avconv are primarily Linux utilities there are ports for both Windows & Mac-OS/X (plus others).
Since this is command line stuff there are no exciting screen shots but I recently used:
avconv -i 00001.mpeg -ss 00:00:10 -vf "transpose=1" FirstDance.mpeg
To do exactly what you are asking for on a video of a wedding reception party that needed to be rotated 90° and that I needed to skip the first 10 seconds. A tip for you - first use the tool to extract a 10 second section of your video into a new file called short.mp4 then play with the options using that file - saves a lot of waiting to see if you got the right settings.
There are also a number of front end GUIs that expose (some of) the functionality of the command line tool.
The web sites for downloads & documentation are avconv & ffmpeg.
A word of caution - you are not supposed to use either of these in some jurisdictions due to questions about software patents of the video codecs.
