Righto, as per usual here is the disclaimer - doing this is risky and you do so at your own peril! Don't come crying to me or Paul @ MoDaCo if it bricks your phone (it shouldn't but this is just a warning)
Enough of that you get the idea Now for the fun bit!
First if you are not you'll need VISIONary+ from MoDaCo, at the time of this writing r13 is the latest and is available on page 7.
Please read and check the original post as there may be an updated version. If you are rooted skip to the next step.
This is Paul's guide he done quickly on his G2, it's more of a pictorial guide (same rules apply to the Legend as G2 in this case).
Once installed use the Temproot option, this can take 15 seconds or so to complete, use a Terminal Emulator and type su then return/enter and your $ should change to a # - this means you have temproot.
Go to the market and install SuperUser, Titanium Backup, BusyBox.
Open Titanium Backup allowing it root access when prompted, go to Backup/Restore and scroll to find one of the preinstalled bloatware apps, I chose the Vodafone Music app and the Vodafone Web app.
Long hold on the app you want to remove and scroll down a bit and choose the option "Force remove app (by recovery exploit)"
This will reboot your phone TWICE, you will get the recovery screen up - LET IT RUN IT's COURSE! DO NOT INTERRUPT THIS.
Once it boots back into your normal check that the app is no longer in your App drawer
Repeat for all the Apps that came preinstalled that you don't want, just be careful you don't remove anything that may still be needed!
A huge thanks to Paul at MoDaCo for this ingenious hack and the Titanium Backup, BusyBox and SuperUser developers for their hard work in writing their apps which also allow us to easy do this
Oh and you can use the Temproot on boot to have a sortof but not fully permaroot