Let's start with the NES problem. I already know that it has 56 colors, 25 of which can be displayed at once in eight four-color palettes (with one palette per graphic tile) and one background color.
The question is, can there be a ninth four-color palette if it consist of colors that are already used on the other palettes?

Then the EGA question. I know that it has 64 colors, 16 of which can be displayed on screen at once. How many colors can one game object or tile have? Can, for example, the player character use all 16 colors at once too? Do EGA games use the 16x16 pixels tile system like NES games?

NOTE! Some of the posts below are misinformed because I accidentally confused EGA with CGA, hence the incorrect topic title.

CGA didn't have 64 colours, it had 16, and with the exception of the 160x100 resolution, most of the resolutions could only use a fixed palette of four colours - the most common being that dreadful looking purple, cyan, white and black.

CGA didn't have any kind of internal accelerated sprite handling that it's contemporaries such as the NES and C64 had. Sprite handling had to be created manually by the programmer, and so there were no limitations on colour use.

It wasn't actually designed for games, so as horrible as it looked even then, there were some incredible achievements.

jamyskis is right. CGA had only 16 colours, but could use only 1 palette for the entire screen, meaning that you are limited to only 4 colours on the screen at any time (and that's counting black as a colour too). CGA doesn't use tiles (unless you count text mode) or have hardware sprites - the whole screen is just one big canvas full of pixels. It's basically nothing whatsoever like NES.

As for your first question, I'll have to remember a long way back to when I did some NES dev but I seem to recall both tiles and sprites having a 2-bit palette selector, meaning you get 8 palettes max. You could do some tricks, like layering multiple sprites over one another to simulate as many as 12 colours to a single sprite, but your sprite budget is limited. You could layer that in turn over a tile, effectively making a single 16-colour tile at the cost of 1/16 of your OAM.

You could send a composite signal through an RCA output though, which gave you the full 16 colours. However, there were only about 30 or so games that actually supported it, and most of them came out when EGA was already well established.

Apparently a couple games abused text mode to simulate a bitmap with 16 colors on a CGA digital monitor. Pretty impressive, I wished I knew about them back in the day.

http://www.mobygames.com/featured_article/feature,10/

Ahhh, CGA Graphics! Most games used one of two "modes". Cool colors (Cyan, purple, white, black) and warm colors (Orange, red, green, black).

God they sucked...

*favourites the thread*

I find old display modes fascinating for some reason, despite growing up in the 90s.

Wow, that's interesting stuff. I didn't know you could abuse CGA like that. Probably because EGA was already mainstream when I was a child (and you could do some devious things with EGA).

Oooh no! I've made a horrible mistake.... I meant EGA and not CGA! What a blunder.... Gonna fix the first post now. Sorry everyone.

Thanks a bunch Barefoot_Monkey! Now both of my questions are answered :)
Oh wait, one more question: In the case of NES palettes, is transparency considered a color? So you can only have palettes like this, red, black, yellow and transparent and not like this, red, black, yellow, white and transparent. (I know the NES doesn't have a pure yellow color, but I'm calling it that for clarity's sake)

Yes, I believe you have the right idea. Palettes contain 3 custom colours instead of 4 because one of the "slots" in each palette is permanently reserved for transparency. So in the pattern table, a 0 represents a transparent pixel and a number from 1 to 3 represents a coloured pixel (where the actual colour is defined in the palette).

Can the transparency be replaced with a fourth color in background tiles that don't need transparency? To me it sounds logical that, for example, a 16x16 pixels brick wall tile could have a fourth color that way.

Well, there's a shared background colour for the entire screen. All "transparent" pixels in background tiles appear that colour (unless there's a sprite behind them). If you're clever enough with your choice of background colour then you can end up effectively with lots of 4-colour background tiles.