You don't need a MS Windows license to use the MS fonts, but you need to agree the
EULA prior to using them.
That would be nice to see the RedHat fonts indeed. They were supposed to be adding hints to their fonts by the end of the year.
These are fonts that I like in Linux: Luxi family, DejaVu family, and to some extend, Nimbus family.