For the first year we kept both my dogs in a kennel when we weren't around. As soon as we let them out we took them outside. When they went we gave them treats and praise. If they did it in the house we gave a firm low "NO", but didn't rub their face in it or anything.How do you housebreak a pet, by the way?
Both of my dogs haven't done anything in the house for years. So I guess that method works.
We were told that rubbing their nose in it really just makes them afraid to go no matter what and that obviously causes problems.
Dogs are great, but you have to make sure they know you are in control.
As for exercise, find a game the dog likes. Tug-O-War, Frisbee, Fetch, etc. It is much easier to tire a dog out doing something he really wants to do.