How about a style that you like but that isn't too complicated? It will be a big confidence booster if you produce something pretty good on the first try. Maybe stay away from really big beers, adjuncts, and extras like fruit, coffee, chocolate, liquor, etc.
It was dumb luck, but for my first brew I chose to do a hoppier than normal amber ale with just cascades. It was nothing amazing, but it was much better than what I thought was possible, having had no homebrewing friends at the time. It really got me jazzed about the hobby.