I would not go too cheap, though I agree that for recreational purposes one probably doesn't need the latest and greatest and most exotic. On the other hand, some of the small differences in quality and performance that you may not notice at first can become more and more noticeable after a couple of thousand miles. Good bearings, shifters that work well (and these days that means also integrated brake/shift levers that don't wear out and fall apart in a year or two), a good saddle, etc. If you keep the bike for a few years, you may find yourself wishing you'd thrown just a few more bucks into it, and one, and the object here is to have something that you like, that makes you want to ride. If you're on a budget, and like quality more than flash and newfangled technology, you might be happier with a really good quality older bike than a cheaper new one, and a cheap new bike may be poor economy if either you end up hanging it up unused, or if you have to upgrade or rebuild too many components.
I also don't think the "heavier means more exercise" argument is very compelling if you're actually planning to ride and keep riding. While it's true in some degree, don't take it too far and let yourself be talked into getting a really cheap department store bike instead of a decent frame.
I would strongly advise going to a good shop and having an expert help you get the right fit. If you have a good fit, you'll ride longer, faster, better. I don't know where the original poster here is located, but here in the USA I've seen a couple of different systems used. One, called "Fit Kit," uses various measuring devices and formulae to determine frame size, saddle height, etc. Serotta also makes a special adjustable frame for the purpose, called a "fit cycle," which I've seen at many places. Long ago I was "fit kitted," and I think it helped a great deal.
Finally, take some of the opinions, if not all here, with a grain of salt, depending on what kind of terrain you are planning to ride in. It's all very well to say you could ride a used Huffy from one end of Florida to the other, or from one end of England to another, perhaps, but if you live in New Hampshire or Vermont, you need something that you can crank up long hills, control on narrow, bad roads while dodging semi trailers, and whose brakes will still be braking at the bottom of Breakneck Hill.
I'm a retro cyclist myself, still riding an 87 Cannondale that I bought back in 1988 from a Category II cyclist who got a new one from the manufacturer every year. At the time it was more exotic and better equipped than I really deserved, but the quality of the components has paid off over many thousands of miles. I also perversely like the bone-breaking, tooth-loosening harsh ride that made early Cannondales notorious.