Technically, I did my first night dive at Hoodsport, Washington. It was mirky and dark with very bad visibility and there was nothing to see. We followed a line down from the beach, single file, through the layers of muck. I could only see my buddy's fins every few moments, but had to be close enough that I was worried he would kick my mask. Once we dropped below the layers of muck, visibility improved to maybe 8 feet. I saw absolutely nothing, and we returned to the surface within 25 minutes. It was not fun, but I doubt that had to do with the 'night' aspect.
I consider my first real night dive to be the Tug Boat in Curacao. It was much more interesting! We saw lots of cool stuff, including some cuttlefish. Visibility was great (compared to Hoodsport), and I enjoyed this dive very much. Yes, I was very tentative, and I stuck close to my buddy and the dive master. My biggest fear was navigation. I prefer to know my own way around, and am uncomfortable if navigation is difficult. Navigation at night is difficult, but I discovered a few things that made it easier. I've done about 10 night dives since, and recently did a couple without a guide.
1. Dive at a familiar site. Frequently, dive ops will take you night diving at the same spot you dove that morning.
2. Pick a dive boat that lowers a light into the water. I'm not sure how common this is, but it provides a great navigation reference.
3. Use a dive guide, and follow them around. It takes away a lot of apprehension.
4. Get a good bright light. Rental lights usually suck.