Cheap usually --> uncomfortable and lousy bearings. You'll quickly learn to hate in-line skates if you buy crap ones. I say look at $100 and up if possible.
Lace up is a pain, but often more comfortable. Hockey-specific ones are are usually like their bladed brethren. Uncomfortable until you start spending $200+. I own lace -up non-hockey blades. I'd try out 5 or 6 models and buy the ones that are most comfortable.
Make sure you get ABEC-3 or better bearings, or ABEC-1 in the very least. Below ABEC-1 the bearings truly suck.
I like the heel brake, but to have a removable one is ideal, esp. if you may want to play hockey or something later. Also, if you want to play hockey, the option to rocker the wheels is a big bonus. (With the wheels rockered, emulating the curve of a hockey skate blade, the in-line skates become MUCH more maneouverable, albeit less stable.) I like to play hockey with the heel brake unlike most people. I'm not a good hockey player, but I'm an OK skater. I have actually learned to use the brake not as a brake only, but also for quick moves. On the other hand it TOTALLY screws me up in the winter - I invariably try to use the non-existent heel brake the first few times I try to stop on ice. Not pretty. At least that's better than trying to use the ice-skating scraping type stop on rollerblades. Now that's painful.

What I hate is those brakes that move with some sort of lever system built in - meant for beginners but when I was learning I thought they were the stupidest things I'd ever tried. I much preferred the simple non-adjusting brake. I think those levered brakes actually hinder progress when learning to skate.
Helmet & wrist guards are
absolutely necessary. Wrist fractures are very common. Head injuries are less common but potentially much more serious. Knee pads and elbow pads are a big bonus too.
Grass is your friend. Start somewhere where there is grass at the edge of the pavement.
Edit:
As far as speed of stopping is concerned people state that you can't stop as quickly on the heel brake as opposed to using the turn stop. Perhaps, but I can stop pretty damn fast. When I go full speed, I can actually put ALL of my weight just on the one heel. My other leg is off the ground, as are my wheels of the foot with the brake. Definitely not for beginners though.
I find it's much harder to stop as quickly using the heel drag method, and it takes much more effort. I find the turn stop method problematic when going full speed too, but that may partially be because I haven't used it as much as those who are forced to use it.