Yes, you will need to unlock your phone....whichever rom you decide to go with, the chef typically has instructions on flashing and unlocking on the first page.
I suggest (and have tried) MightyROM, Fusion, Xpressyourcell or Mr.X....You will have to review all the roms you're interested in and see which one fits your requirements. Also, the folks in each of those threads are extremely helpful if you should run into problems or have any questions regarding the roms.
Hope this helps....
EDIT: Check this link for a review of the some of the more popular roms...
http://forum.ppcgeeks.com/showthread.php?t=114078
Oh yeah, you can always go back to stock and relock your phone.