Choosing a breed

First, NO dog should be trusted loose with a hamster.  They are hunters and hamsters are prey animals.  No matter if you have a Chihuahua or a Jack Russell.  I have two Russells and I have trained them to ignore my small animals in thier cages, but when they come out, the dogs go in another room and are locked away from all small animals. 
Next, there are MANY different types of terriers.  From the small Norwich and Norfolk Terriers, all the way up to the large Airedale.  But, as a group, they are generally quite prey driven...plus, they are not usually the easiest to train if you haven't had a dog before...very independent.  But, a very fun challenge!
Labs shed A LOT!  They also take a long time to mature past the puppy stage. 
Springers might be more high energy than you are looking for.  They are hunting dogs and I haven't seen too many that have made the full transition from hunting dog to family pet yet.  Golden Retrievers are hunting dogs, but they are also being bred mostly for companionship, Labs also.  There aren't a ton of hunting breeders around now. 
If you haven't had a dog before, your local shelter, or petfinder.com, might be a good place to start!  You can also find breed specific rescues with purebreds that are past that annoying, chew everything in sight, pee and poop on the floor, cry in the crate stage.  Puppies are great and very rewarding, but they are a lot of work, and if this is your first dog, you might want to consider a young adult whose temperment is already known.  Then, sign up for a basic obedience class.  It will probably be the best investment that you ever make.

I'd agree with the small animals.  Breed doesn't matter.  All prey animals should be kept in a room that can be closed off when your not watching the dog or the dog should be shut in a room away from the small animals when you are not watching.  You wouldn't believe the number of posts I've read where someone that had a sturdy cage up high on a table with a small dog that didn't usually pay any attention to the small animals left them unsupervised one day for just a half hour or a couple hours and came back to find all their small pets dead.  There are also a few dozen more where you could have seen it coming.  Medium-large dog that for years was very nice to the small pets or ignored them left in a room with cages on eye level and there's a cage full of dead gerbils, guinea pigs, rabbits.  I could dig up all the posts off the guinea pig forum I go to if you want proof.  Personally I will never ever have a dog of any breed or personality in a house with small pets unless they have their own room with a solid door.  Currently I have 3 guinea pigs, 2 gerbils, and 2 degus and there is a room designated the small pet room.  Zami is allowed to enter the room when I do and required to leave the room when I do or when I say "out".  Even if I'm just going the 8' to the fridge and back through the door Zami is required to exit the room with me and can only enter again after I do.  Despite the fact all she does is sit and watch the pets even if the guinea pig cage is left open she is absolutely never left unsupervised on the same side of the door as a prey animal.
 
Cats just come down to training.  Any dog can be trained to live with cats and any breed can have individuals that will harass cats.  That depends on how they are trained when around the cat.  Most puppies see cats as toys or playmates so you often have to keep the pup on a leash constantly when the cat has access to the same room.  Give them a command for not bothering the cat such as "leave kitty" and praise when they ignore the cat or walk around it through a room instead of trying to sniff and play with it.  It takes longer for some dogs than others but eventually if they are never allowed to be rough or chase cats then they will learn to coexist at least fairly peacefully.  However there are some dogs that it's near impossible to train out their instinct to chase.  If cats run outside it's entirely different than walking around inside and hunting dogs can require alot more training to keep them from chasing.
 
My opinion is that if your looking for a pet unless you have a specific breed or type of dog already in mind your best off going to  a shelter and finding a mix.  Ask lots of questions, see if you can take the dog home for a trial, and your sure to find one that fits all your requirements.  Even in a purebred the personality can vary considerably so unless your set on a certain breed or need the dog for a specific purpose and are willing to work around that dog's individual traits your better off looking at adult or at least somewhat older puppies at the shelter.

ORIGINAL: Sham85
My opinion is that if your looking for a pet unless you have a specific breed or type of dog already in mind your best off going to  a shelter and finding a mix.  Ask lots of questions, see if you can take the dog home for a trial, and your sure to find one that fits all your requirements.  Even in a purebred the personality can vary considerably so unless your set on a certain breed or need the dog for a specific purpose and are willing to work around that dog's individual traits your better off looking at adult or at least somewhat older puppies at the shelter.

Even if you are looking for a certain breed, there are many breed specific rescues and it is very easy to find most breeds in a rescue or shelter.  Not all dogs in shelters are mixes.

Most are unknown though.  Even in breed specific rescues you'll see alot of possible or known mixes.  Very rarely do they come with papers or proof that they are purebred.  Therefore you can't assume they are.  I did look at some breed specific rescues before getting a puppy from a breeder and probably no more than 1 in 10 were actually known purebreds while over half were obvious or known mixes.  Not that I cared that much if the dog had papers I just didn't find one that really got along with me and my life.  If your looking for a purebred then breed rescues aren't much more likely to have one than local shelters.

Yes, please consider checking out breed rescues and browsing through [linkhttp://www.petfinder.com]Petfinder[/link]. I think a young adult or adult dog whose personality is already known will be a great match with you.

I don't know which breed is best for you, or if you'll find this helpful but we have two Goldens and one GSD...we knew a lot about each breed rior to bringing them into our home and still did more research.
 
If we were going to get a breed of dog that we didn't know much or anything about, we'd do plenty of research but also go to dog shows, ask questions, visit breeders, and find a few owners of the breed and spend time with them and their dogs (varying ages) to see what the breed is all about...in it's environment, with us, other people/children/dogs, etc and daily life.  And then, the big question for us to answer would be: can we provide what the breed needs to thrive and be healthy?
 
[]  ...good luck in your search!

ORIGINAL: Sham85

Most are unknown though.  Even in breed specific rescues you'll see alot of possible or known mixes.  Very rarely do they come with papers or proof that they are purebred.  Therefore you can't assume they are.  I did look at some breed specific rescues before getting a puppy from a breeder and probably no more than 1 in 10 were actually known purebreds while over half were obvious or known mixes.  Not that I cared that much if the dog had papers I just didn't find one that really got along with me and my life.  If your looking for a purebred then breed rescues aren't much more likely to have one than local shelters.

I find this statement to be false in many cases.  There may be some rescues that have many mixes, but most have lots of purebreds.  You don't have to have papers to prove that the dog is purebred.  Papers only matter if you are going to show or compete in performance events.  Here are some examples:
review=>http://search.petfinder.com/shelterSearch/shelterSearch.cgi?animal=&breed=&age=&size=&specialNeeds=&declawedPets=&children=&status=&id=&internal=&contact=&name=&shelterid=OK31&sort=&review=
review=>http://search.petfinder.com/shelterSearch/shelterSearch.cgi?animal=&breed=&age=&size=&specialNeeds=&declawedPets=&children=&status=&id=&internal=&contact=&name=&shelterid=OK130&sort=&review=
review=>http://search.petfinder.com/shelterSearch/shelterSearch.cgi?animal=&breed=&age=&size=&specialNeeds=&declawedPets=&children=&status=&id=&internal=&contact=&name=&shelterid=KS133&sort=&review=

Purebreds can EASILY be found in rescue.  No, most won't have papers, but papers still don't prove that a dog is purebred.  Especially with some of the less than reputable registeries, I've seen people forge papers.   A lot of what you said may be true in the rescues you looked at, but it is NOT true in all rescues.  It would be like me saying "All pit bulls bite" or "all Goldens are crazy hyper."  Some of them may, but definitely not all of them.  Please don't lump all rescues into one category.

I will not call them purebreds if they do not have proof in some way.  Just the previous owners saying it's purebred or the rescue not seeing any other mix does not make a purebred.  Granted there are some false papers out there but without papers I will not call an animal purebred.  They are all probably mixes to me.

I'm having trouble thinking any breed is going to be awesome in this situation.  The small animals are the kicker, you gotta expect to have the hamster contained and for highest likelihood of success with the cat, you should start with a puppy.  My mals, high prey drive, were great about the hamster in his cage but I know 100% they would have eaten him if he had gotten out.  All dogs either shed or have to go to the groomer---that's reality.   
 
Labs ARE high maintenance, you have to exercise them or they get nutsy.  While that's true for pretty well any dog, it's especially true of the hunting breeds as they were afterall bred to hunt! 
 
What about a smooth collie?  They're not THAT big really and they may herd the cat but may be less likely to hurt the cat.  They seem like wonderful dogs, rather calm, intelligent.  Or the setters, I don't recall mine shedding that much and she was awesome with the cats.  She was very intelligent and she didn't run off, either.  I'd look more at the field bred lines, it seems they're a bit healthier.  If you're going to be getting that many walks in plus fetching, that should be good. 

<----- Purebred black and tan coonhound. He is absolutely the breed standard in every way, could be a bench dog if he had his papers and wasn't neutered, and has tattoos in his ears from his original breeder, a breeder of UKC working coonhounds in Southewestern PA.

Adopted from a shelter.

If it looks like a duck, and walks like a duck, and swims like a duck, it's a duck!

ETA: On the purebreds in shelters/rescues topic, not recomending a coonhound for this household, just to be clear.