I truly tried my google-fu, but couldn’t find an answer…kind of a vague question anyway, I guess, but perhaps there are some fellow geo-geeks or folks with local knowledge here that might know. I do know that on I-40, once you get somewhere past Oklahoma City, you start seeing these sorts of features, but I’d bet there are some that occur a bit east of there. Any ideas or even random references to oddball geographical features are welcome, too. Thanks!
Just a bump in case anybody might have an idea. I might resort to some Google Earth-ing and come up with some possibilities.
Not sure exactly about physical geography, but I’ve seen cactus on the east coast in either NJ or Pennsylvania.
As you head north from New Haven, CT, on I-91, you will see a butte-like structure on your right.
The Mt. Holoyoke Mountains (Western MA) have columns reminiscent of Devils Post Pile in Wyoming.
And Purgatory Chasm (Central MA) looks like a western box canyon.
Settlers on the Oregon Trail took Chimney Rock in Western Nebraska to be a sign that the East was truly behind you.
The Badlands in South Dakota are pretty Western-y, and are further East than Chimney Rock.
Map
Possibly of interest,
This is probably not quite what you’re looking for, but Seneca Rocks in West Virginia is one of the most “Western”-looking formations I’ve seen in the eastern U.S.
Natural bridge VA http://www.virginiaplaces.org/geology/naturalbridge.html
Of course, it would look more “Western” if it wasn’t for allt hat lush vegetation 
Many features that we think of as looking “western” look that way because of a combination of two major factors: geology, and vegetation. Vegetation, of course, depends greatly on rainfall (and temperature).
In other words, there are examples of typically “western” geologic features further East, but they tend not to look so western because of the green, lush vegetation on and around them. So, you’re right on about a north-south line cutting through Oklahoma City as being just about where the rainfall gets low enough (as you move west) that things start to look more “western”. (Notice how this is a northward continuation of the western edge of the Gulf of Mexico. No coincidence – that’s where much of the moisture east of this line comes from.)
That said, allow me to mention Chimney Bluffs, on Lake Ontario in upstate New York, as a quite Western-looking landscape.
And a Helluva Good place it is too!
Any answer would have to be ambiguous partly because how geogrphical features are labled is determined largely by culture. The word “mesa” (Spainish for “table”) was adopted as a name for a type of flat-toped hill found in certain parts of the western United States, but that doesn’t mean that their aren’t hills in other places which look very similar, even if they aren’t given the same label.
Thanks for the interesting posts, folks! I agree with JKellyMap that more than geology defines the “westernness” of the terrain. We have canyons and gorges and eroded sandstone, etc. in the eastern US, but the vegetation makes it different. I like those things, too!
For instance, the Ozarks are an eroded plateau, and if not for the vegetation, some areas would look like canyonlands**. **There’s a flat-topped mountain that dominates the landscape in my hometown that looks a lot like a mesa, Mt. Nebo.
In Oklahoma, things really start looking that way somewhere in the middle of the state. The Wichita Mountains are pretty western looking, and the Glass Mountainsseem pretty full-on. Both of them are around that prairie/plains divide.
What’s a hoodoo?
Bryce Canyon is the prototypical example of hoodoos.
It seems like the “Western” formations mostly start along a line running through extreme western North and South Dakota (Badlands), Nebraska (Chimney Rock), Kansas and Oklahoma, and western Texas. But there are isolated formations east of that line, such as these pedestals in the Ozarks.