depends resizing you would like to do, if you want to make a big image small then download something like gimp and you can resize the image very easily with much to any quality loss. But a small image to big, will no matter what program you use, it will turn very pixelated the larger the picture gets. Unless you have a vector image instead of pixel image it will always lose some quality when being resized.
Best thing to do is download Gimp, its pretty much a free version of Photoshop.
Yep, Photoshop or Gimp are the only ways to go. Also, make VERY sure that you're using the same image proportions otherwise you get a scrunched image like you have where people are too short and fat because theres too much vertical compression to match the horizontal, or they're too skinny because theres too much horizontal to match the vertical. Photoshop makes this nice and easy with a check box that says "constrain image proportions" when you resize. Photoshop also offers several things to reduce pixelation, such as various filtering and resampling methods which can work better for enlargements, reductions, etc.
The drawback is that photoshop can be ridiculously expensive. Unless you have several hundred dollars laying around, go with Gimp. It's free.
Unfortunately, no. I dont use Gimp and have no idea how to use it. However, I know theres about a thousand people around here that do, so I'm sure one of them could help. If it was photoshop you were looking for help with, it'd be a different story. Sorry dude!