Interesting question about beginnings in first person novels at the Absolute Write forums here:
http://www.absolutewrite.com/forums/showthread.php?t=197912
Beginnings are hard enough when you write in third person, but when you can't even say the name in line one or hint at gender because you are using "I" instead of "he", it sucks that much more. It is even harder when you can't just skip the beginning and write it later when you know what your novel is really about. With my new method of writing, whether I write beginning and ending first or just all key plot points, I can't skip the beginning. It must be written. And it must work, because around it and other plot points, I flesh in the novel. Then let's not forget the problems that occur if this is not the first novel in your series.
It's tough, writing beginnings.
How do you do it? By not trying to stuff a ton of stuff in a paragraph one. Besides giving a picture of where my characters are, the key thing I seek to explain is gender. My main characters/pov characters are male. I'm not. And I sometimes put them in situations where the default expected gender is not male.