In contrast to Matt3989...
I started without a kit, and I don't see the advantage of kits. It's not very hard to find a recipe and order the components. Ok, I guess it is a little bit easier, but if you don't order the kit, you won't get the useless sheet of bad instructions that you'll have to use your willpower to ignore. Otherwise, as long as you're getting your kit from a reputable source, it really is just the same stuff you'd buy if you were putting together the same recipe yourself.
I do think starting all-extract plus specialty grains is a great idea. Managing a mash is not hard, but it's one more fiddly step that you have to plan and worry about. Better to focus on the boil and sanitation for the first time, then add complexity.
My first batch was an ordinary bitter, made with steeped crystal, DME, and hops. I used Nottingham dry yeast. For my recipe, I looked at a bunch of sources, probably using Papazian's book for the most inspiration. Picked out an OG somewhere in the middle of the style range, which was 1.035 or so IIRC. It's low gravity, and Nottingham is voracious, so I chose this style because it was very unlikely to stick.
The only speed bump here is that, from what I'm told, Nottingham can get weird at normal ale temperatures and wants something colder. For me this wasn't a problem because it was winter and I was fermenting in my garage, so it was a big effort involving a fridge and bottles of hot water to keep the temperature that HIGH. You might want US-05 or S-04 if you're not confident that you can keep your fermentation temps down, I think they're more tolerant.