I like the charging dock. The first generation iphones came with it, not it's an accessory. It lets you iphone stand upright while charging or synching with itunes.
Congrats on the new toy! I looooooooove my iPhone. As far as other accessories, you might consider getting a dock for the car if you plan on using the phone to listen to music in the car. If you have an aux input in the car, you can get a dock from DLO or Kensington or another company that will cradle the iPhone and allow you to listen to music using an aux cable (runs from the dock to the input). It also charges the phone while you drive. They can be a little pricey, but the sound is SO much better than one of the FM transmitter docks. They can also be used with a cassette adapter if you don't have the aux input and don't want to go the FM transmitter route and still happen to have a cassette deck in your car.
This is the one that I have. I originally had this one, but it seemed that the the jack thing fit too loosely into my AC adapter and therefore was "wobbly" when supporting the weight of the iPhone. It worked fine with my nano, which is what I usually use in the car anyway, but I wanted one that worked with both so I ended up giving the DLO one to my mom to use with her nano.