For dealing with walkable/not-walkable areas, I'd recommend dealing with the coordinates directly (presuming that you're actually moving the sprites) and maintaining that info seperate from the VRAM/Name tables. If you're doing an RPG system, I'd keep a highly compressed version of the tiles in RAM or ROM and check against that instead.
There is no way (in software, at least) to get finer color resolution than the Attribute tables provide. You should design your maps with that in mind. (The attribute tables scroll with the name tables, so that, at least, won't burn you.)