If you’re starting off by going down I-95, stop at Carl’s Ice Cream at the north end of Fredericksburg.
Go see “Digger’s Dungeon”, home of the Grave Digger monster truck! Roadside America page about Digger’s Dungeon
I haven’t stopped there, but friends have and liked it.
Don’t stop at the Weeping Radish Microbrewery in Grandy NC. They make a great sausage, but the beer is average and the rest of their pub food is just OK.
I’m very confused. If you went by South Of The Border en route from NoVA to Outer Banks (which are the northern and central portions of coastal North Carolina) you were really lost.
That said, if you are going by SotB it’s worth pulling off the road briefly there.
For more historical stuff, and depending on your route, the area around Hampton Roads has several options, e.g. Yorktown, Colonial Williamsburg, the Jamestown colony, and so on, which can kill a few hours. Not tacky though, if you’re looking for tourist traps, those aren’t your destination.