"Editing the background" is a little bit complicated... but I would recommend Adobe PhotoShop. It's a couple hundred dollars though. You can use the pen tool to isolate your subject, put it on it's own layer, drop in your new background layer, and then use another tool to blend in (the legs or whatever).
GIMP is free and similar to PhotoShop, I'd also recommend that one!
I've been using Photoshop Elements for years. It's the baby brother of Photoshop. It runs less than $100. You can download it from Adobe's site and use it for 30 days to see if you like it before buying. Sam / Costco / BJ's often have them for good prices.