You could do an non-regular tile map. You could use variously sized bitmap elements to build a map. Nothing says you have to use 32x32 or other regular sizes.
Would use more RAM than 32x32 tiles but less RAM than a super-sized bitmap.
Would use more RAM than 32x32 tiles but less RAM than a super-sized bitmap.