Here's my 2c worth, I got my legend with eclair on it then when I heard about froyo couldn't wait for it. Once I had it I was happy games worked better every thing was cool.
My wives HTC desire HD got the gingerbread update then I was jealous, and was sad when I found out I wouldn't be getting official gingerbread too. That's about the time I found out about ogo2's gingerbread rom (the only reason I actually ended up rooting in the first place). From that time onwards I spent months on xda reading and learning stuff before I rooted.
Taking that step was huge for me & because I was on froyo with that dreaded hboot 1.01 which made rooting so much harder.
What I did was read the guide many times over, downloaded all the files required and did many dry runs of the rooting process stopping before any changes to my phone was made gaining confidence to actually do it.
Once I did it and flashed my first rom I never looked back, I've now flashed pretty much every rom on xda (except the eclair based roms).
When the hboot 1.02 was released and before blay0 pointed out you don't need to go back to stock, I unrooted my phone and when back to stock, and man that only just confirmed why rooting was the best!
If you are hboot 1.01 best method is to do the hboot 1.02 thing, if you are on hboot less than 1.00 then do the s-off method for your hboot version.
So long as your careful, take your time, read up on stuff on xda, do Google searches for stuff too and if your really stuck ask questions, I don't think you'll regreat rooting your phone...
The issue regarding cm well yeah it makes a huge difference over stock but just remember cm doesn't have sense so will take a bit of getting used too comming from stock rom.
sent from my legend, currently using zeubea ics beta0
Update: 17th november 2013
Samsung G S4 stock BMG4 + root
with cf-auto root + philz recovery.
HTC Desire HD
(Hboot 2.00.0029 AND S-OFF)
SVHD V 2.1.0
Retired HTC Legend