From my own experience (199cm, quite fit but 'semi-athletic' 120kg): For £500 - £750, you won't have that much choice!
The most important aspect are wheels, and despite extensive research, I haven't come across a suitable "off-the-shelf" setup. Instead, I use handbuilt wheels, 36 double-butted spokes, deep profile rims, quality hubs. I currently have these in use:
http://www.rosebikes.co.uk/product/detail/aid:339581
The other pair I have ordered is the aid:339609. The 105 hubs seem to be identical to the Tiagras, but I have chosen them for the "all black combination". I've combined the wheels with 25/28mm slick tires. The difference in rolling resistance is neglectable, but comfort and protection against pinch flats is much better. The wheels took quite a few beatings from pot holes on longish night rides with added panniers, i.e. the London to Brighton and Dunwich Run. They are still true and fast. I also hadn't any broken spokes since using the replacement wheels.
The whole wheel/tire combination will cost you about £150, which leaves £350 - £600 for the bike, maybe less if you want to invest in pedals, shoes, replacement tubes, basic tools and a small computer.
I would suggest you go with a good alloy frame. Some people don't like their stiffness, but what might be uncomfortable at 70kg and small frame sizes gets much more elastic at 140kg and a bigger frame!
The other important part is the crank set and bottom bracket.
I personally went with a Decathlon Fitness bike (Forme 3, was on offer for £200 and is now back to £250). Note that the front wheel has clearance for 25mm tires only, while the rear wheel can fit 28mm. I also needed to replace the cassette as the bike comes with a 7 speed freewheel setup which is incompatible with typical road hubs. This wasn't too bad as I don't need the mountain-ish 14-28 range and have now a 12-21 instead, which gives about the same range as a 20 gears compact race setup.
The Decathlon was a temporary choice while looking into a more suitable race bike, but it has worked so well that I decided to keep it as my future commuting/fitness bike. The bike I've ordered last week is the Radon R1 4.0:
http://www.radon-bikes.de/xist4c/web/R1-4-0---SSV_id_18452_.htm
It is currently on offer for €849 (around £650) plus about £25 for shipping to the UK. You can probably sell the included 20-spoke Mavic Aksium wheels and tires for £150. It has a good stiff alloy frame with a combination of Ultegra, 105 and FSA parts. The FSA cranks are a bit on the heavy side, but I read about a taller Tour rider who actually preferred these for the added stiffness. Regarding frame and part weights in general, you can probably start thinking about these when you're down below 80kg ;)
As you might expect, I can't give you any long term opinion on the Radon yet.
Other alternatives I looked into were the Chris Boardman bikes which were recently on sale at Halfords, except that they are not produced in my frame size.
Good luck!