Cleaning up a photograph in Photoshop

I searched, but couldn’t find anything to help…
What I need help with is this:
I’m putting photographs up on a website for a cilent. They are digital photos that he took himself, but they all look like crap compared to to the old photographs that the original owner took.

I played with them a bit in photoshop, and made them look okay, but still nowhere near the quality of the other photographs. Chances are, the originals were done with a professional, high-quality, expensive camera, but he just has a 500 mega-pixel digital camera. Here are 2 samples:

Originals:

and after playing with it, my image:

What I did was this: I shrunk the original image down to 500px (it was like 2000 something)
I applied Sharpen Edges, and played with levels, and contrast, and colors, etc. Mostly, I do web-images that are made from scratch, not photgraphs, so I’m a little out of my element… is there any concievable way that I can hope to get anywhere close to the other quality? Or is it hopless…
I imagine that with the camera he’s using, that’s about as good as it gets, but I’m not sure… any help is greatly appreciated.