In terms of the rescue/puppy debate it's worth remembering that lots of dogs are surrendered for reasons that have nothing to do with the dog and it's not unheard of to know their background. e.g. we have two JRTs that were rescue and were a year old when we got them. They were surrendered because the owner was moving and couldn't take them and - as it happens - we knew the old owners (the dog's came through a charity but it was a small town) and so could talk to them about where the dogs came from etc. Even without knowing the old owners, the rescue is likely to have got as much as info as possible so they can give you a good idea.
It's also worth noting that not every dog from the same breed behaves the same, so you could not guarantee personalities with a pedigree. Obviously there are trends in breeds but you could still get an odd one that doesn't behave like the others. Bitey's suggestion about carefully considering the negatives is a good one. ALL breeds have bad traits that are no more guaranteed than the good ones, but worth being prepared for.
As an example, my springer is mouthy and chews anything, he is hyper attached to me, chaos on the lead and loses his head if he smells something good. They are all typical traits to his breed and so were something I was prepared for. He is also (true to breed) ultra friendly with anyone he meets, energetic, playful and fun loving, relatively easy to train. Untrue to breed, he shakes anything soft (toys and socks) like he's trying to break it's neck. I blame the JRTs for that 
A puppy will need pretty much day-round care for a few weeks and not all sitters accept young dogs so it's worth considering the practicalities of this before committing to a puppy.
How much exercise you want to give the dog (and what kinds) is key.
Higher energy breeds you might want to research are...
- Keeshond (friendly, smart, easy to train, barky, requires shit load of grooming)
- Labradors (energetic, easy to train, tend to be patient and gentle, bigger than you wanted, can be powerful dogs)
- Airedale terriers (energetic, medium sized, relatively easy coat care, a good all rounder, barky, strong willed)
- springer (show type, not working), have already said a bit about them above, also very energetic and bring mud into the house!
- podengo (energetic, escape artists, friendly, tend to be good with kids)
- Portuguese Water Dog (energetic, friendly, easy to train and smart, can bond with one person more than others, chews)
- Soft Coated Wheaten Terriers have massive fans (friendly, energetic, easy to train, barky, can be destructive if not entertained)
I am not recommending any of those, just giving some options that might be suitable.
Lower energy breeds tend to be companion breeds like the Lhasa recommended above which is a good choice but does take a bit of grooming and are not always great with strangers.
Dachshunds do have delicate backs that need care and can be tricky to toilet train. They don't need as much exercise as those mentioned above. Can be tricky to socialise, barky and dig.
In all honesty, if there was a small/medium dog with average energy requirements, easy to train, minimal grooming, not shedding and great with kids... every family would have one
. In fact, there was the Cav you mentioned which fitted much of that but the health issues have all but ruined it which is a travesty.