After lots of toying around, I think I've made something that might be of use to other people. Basically, I took the cliffs from the BS Zelda tileset/first quest remake and made them use fewer colors because I'm shooting for simpler, swappable palettes and an older-school feel. Maybe these versions will also be of use to someone else.
http://www.arinoru.net/~pteryx/color-reduced-bs-cliffs.png
Oh yes, almost forgot -- the tile immediately to the right of the cave arch in each version is a subtle "cave hint" tile; compare it to tile 2 of row 4 of the 4x4 cliff example. -- Pteryx