Currently, all tiles are equal- they are either passable or utterly impassable. My suggestion is this:
give each tile one more value- the obstructedness of the tile. This is a 0-7 value that slows creatures that attempt to pass that tile.
0=totally clear. 1=90% clear. 4=50% clear... and so on.
After 4, tiles are shown with a dark gray background to indicate lots of obstructions. At 7 units, the tile is fully impassable due to items in it, for instance in a vault of gold coins or in a pile of dead goblins. Possibly, 5 or 6 units in a tile act as a ramp so one could stack crates (or gems, or skulls) to climb a wall, for instance.
The tile occupancy test could happen very irregularly, perhaps scanning a few hundred tiles a frame to avoid too much strain.
Continuing this idea, there is a second element- uneven terrain and dense natural growth.
In places like mountains, tiles would have a pre-set amount of obstructions that could vary- for instance, 1 or 2, to replicate rough terrain and otherwise insignificant uneven eroded areas and loose scree. Similarly, forested areas should grow "dense brush" that significantly slows units that try to pass- anywhere from 1 to 4 units of occupancy. these types of internal obstruction may or may not stack with plain items in the tile.
The amount of slowing in a tile should be visible to creatures so that they will path around unnecessary obstructions (say, for instance, like goblins moving around existing piles of corpses.)
One small necessary add-in: the ability to pick up items from an adjacent tile to enable better clean-up of debris.
Much Later Edit: While I acknowledge that this would most likely slow the game down, possibly by several FPS or more on large maps, I feel that the gain would be worth it- particularly in Adv. Mode, where this would make traveling and fighting in forests interesting and give roads a definite purpose.