If you want to point at stars and be safe, green is the way to go.
In my opinion, 50mW is just right. A high power 532nm or 445nm laser will work but the brightness of the laser may ruin your night vision.
I have a 10mW and 50mW green pointer that I keep in my camera bag. I set one up on a tripod, point them at the object (or in the vicinity of the object) I want to photograph/observe and it makes aligning my camera or telescope much easier.
The 10mW is a little harder to see through the viewfinder/finderscope but the 50mW works very well.
The reason green is ideal is the fact that the human eye is more sensitive to green wavelengths than any other color, which means you can use less power to get a brighter beam.
Another advantage of green lasers is that they have pretty good beam characteristics for pointing purposes. The common 1W+ laser diodes have rectangular beam with a wide divergence angle.
Ibuprofen mentioned red lasers... I like the fact that red wavelengths do not affect night vision as much but the low brightness of 660nm light makes it difficult to use as a star pointer.
I recently put together a 635nm 75mW laser (single mode) for someone else. It is just bright enough to be used as a star pointer, it is very stable, the divergence is very low, and the red wavelength makes it "soft" on the eyes.
A single mode 450nm laser might work equally well but my eyes don't like looking at 450nm lasers for extended periods... it throws off my color perception of greens and blues and makes my eyes feel strained.
In fewer words, I recommend 50mW 532nm or 75-100mW 635nm.
Below is a photo of 75mW 635nm and 10mW 532nm aimed at the Pleiades star cluster.
If I was trying to show off to a super model? I would probably not worry about the laser so much and pay more attention to the girl.
Hope this helps... gotta get back to work now...