My 2 cents: First, a "decent but not unlimited" budget is a bit vague. To the average high school student, that might be $50. To Bill Gates, it might be $50 million. If you could narrow it down, that might help others give better recommendations. Similarly, it'd be helpful to know if you're looking to buy new or used. Most of the replies to date seem to assume used, probably because that's where you can get the most bang for the buck (or Eurobuck, in your case).
Second, if buying used, condition is at least as important as brand. You can buy from a reputable dealer, as others have suggested, or just take your chance on eBay (or wherever), and if you get a dud, try again. Buying locally has the advantage that you can examine the merchandise yourself before buying. That might limit your available options, though. You might want to see if there will be any camera shows in your area in the near future. You might find a good bargain at one.
Third, if you buy used, and
especially if you buy a model that's no longer in production, be sure it comes with all the accessories you're likely to need. These include negative carriers, condensers or mixing boxes, filter holders, etc. Such things can be expensive to add later, especially if they're no longer available new.
Fourth, check on the bulb type the enlarger uses. Make sure it's still available, ideally at a low cost. Some enlargers use oddball bulbs, some of which are no longer available. I've seen descriptions of ways to jury-rig certain models to use alternative light sources, so it's sometimes possible to work around such problems -- but you might as well avoid the hassle if you can.
Fifth, you may want to narrow the field by deciding on certain design features, such as the maximum negative size the enlarger can handle, whether you want a diffusion or condenser enlarger, maximum physical size of the enlarger, etc.
Sixth, the lens is very important, but because used lenses are so cheap today, you shouldn't pay too much attention to the lens that comes with the enlarger you buy. If it's a terrible lens, you can just buy a new one. As has been mentioned, 6-element designs are generally the best.
Finally, as Dave Miller says, most people will recommend whatever they use. In the year or so I've been doing my own enlargements, I've owned two enlargers: a Durst C35 and a Philips PCS130/PCS150. The Durst was the bottom-of-the-line model from about 20-30 years ago. It handled 35mm only, although there was apparently a kit to enable it to do medium format, as well. The Durst C35 had built-in yellow and magenta filters, but no cyan filters. This made it (barely) adequate for color work. Exposure times were a bit long with it, and it used a bulb that's no longer available (although I found an adequate substitute). Mine was showing its age and so I eventually decided to upgrade (hence my writing about the Durst in the past tense; I sold it).
The Philips PCS130 is definitely a
much better enlarger, but it dates from roughly the same era. Equipped with a PCS150 control unit and light source, the Philips uses an unusual additive color system, meaning that it has independently controllable red, green, and blue lamps. (Most color enlargers use a white light source with cyan, magenta, and yellow filters, which is referred to as a subtractive system.) Additive and subtractive systems are both effective for making color enlargements and for controlling the contrast with variable contrast B&W paper. Although there are some oddities in the Philips additive system, overall I find it easier to work with than the Durst's subtractive system. The enlarger's also much sturdier and much more flexible (it supports up to 6x7 negatives with the right condensers, can do wall projection and head tilting for perspective control, and so on). The biggest minus for the Philips is that it uses some rather odd bulbs. They're still available, but they're pricey (~$20 apiece). It's also long been out of production, so if the unit you get lacks accessories you want, you'll have a hard time finding them. If you're interested, Yahoo has a
discussion group for these enlargers. The PCS130 itself was reportedly made by LPL, with the electronics in the PCS150 made by Philips. These were also sold under the Paterson brand name. The PCS2000 is a similar enlarger, but it uses a diffusion design rather than the condenser system used by the PCS130.