I was stationed at Camp Lejuene from 1993 to 1994. Although 20 years ago, I bet not too many things have changed. You first need to get on the base. I did many, many long runs along the roadside there, in the grass just alongside the road the Marines would cut about once a week. From the main gate toward the track, there is about a four mile stretch where there is a nice dirt / packed sand path that paralleled the main road. It was nice, with just lots of little roller coaster hills. There is a tartan track there that I hope is still there. It has exaggerated drainage allowances, so the track feels a bit funny. There are a ton of great tank trails to run on, but they can be muddy. From the main gym, there was a paved running path that everyone would run out and back about six miles. It was quite an ego boost to continually pass people mile after mile even just running 6:15's.
There used to be a marathon on the base in the spring and a half marathon in the fall. There is also a great big grass field near the track that is about 1400 meters per lap. Great training on that field and the grass was always kept short, but it would get muddy whenever it rained. Off the base, the running is really tough because the shoulders on the roads are narrow. The other poster who said that you'd be the fastest guy in town may be right. However, when I was there, I was five years out of college, there would always seem to be some kid straight out of high school who ran sub 4:20 / 9:20. So don't get too comfortable - some eighteen year old kid may surprise you.