No, they really didn't. It didn't take a noticable amount of extra CPU power to handle looking up a table of which palette from memory to apply to the 4-color tile or sprite. And that's all the memory it needed too, 4 bits per tile and 4-bits per sprite, plus the 32 bytes of palette registers (eight 16-bit palette entries for backgrounds, eight 16-bit palette entries for sprites). Just to add color, Nintendo didn't need to triple available memory, double the CPU speed, add DMA's, allow larger cartridges, etc. As a developer, we considered the GBC a true successor to the Gameboy, and we pushed the system as hard as we could, there's no way the original Gameboy could have run the Harry Potter RPGs (especially Chamber of Secrets). And the reason early games were on dual-compatible cartridges wasn't a dictate from Nintendo, it was "gosh, there are millions of original Gameboys on the market, and only a few Gameboy Colors - let's earn tons of money!"
Nintendo didn't want developers *only* adding color, they wanted them to make it obvious the game was improved by being on GBC. From the official GBC dev doc:
This was different from DSi, the DSi Nintendo didn't want end-users to even know it had extra power, if the same game was on both DS and DSi, it was really only things like the camera they wanted developers making a point about. And on that system it really did take extra power to crunch photographs in real time, especially if you wanted to do something cool like apply a sketch shader to them (as in Assassin's Creed 2: Discoveries).