How can you render an area with colored tiles, (10-20x10-20), faster than with regular quads/triangles with a call to glColor3ub with each. I’ve tried with triangle strips, but then you can’t make each tile an individual color, because the vertices are shared 
Can you do it while keeping on a simple level like strips or should I begin learning VBO or vertex arrays?
I just don’t want to learn VBO, right now, if it doesn’t affect the rendering speed which don’t think it would with only 100-400 polys on the screen for the tiles plus a couple of hundreds extra.
Use vertex arrays and render indexed triangles. You should end up with four vertices per tile.
A---C E---G
| /| | /|
| / | | / |
|/ | |/ |
B---D F---H
ABCD need to have the same per-vertex color – the color of the first tile, obviously --, and EFGH get the color of the second tile.
You could render these two tiles like this:
glColorPointer(<...> );
glVertexPointer(<...> );
glEnableClientState(GL_COLOR_ARRAY);
glEnableClientState(GL_VERTEX_ARRAY);
static const GLushort indices[]={0,1,2, 2,1,3, 4,5,6, 6,5,7};
glDrawElements(GL_TRIANGLES,12,GL_UNSIGNED_SHORT,indices);
If I understood it right, you only need solid colors.
For a regular 2D grid, the simplest method is to use one GL_QUAD_STRIP per row.
For the color, use flat shading with glShadeModel(GL_FLAT) and only the color at each last quad-vertex will be used to color the whole quad, that means each quad in a quadstrip has a single color and it’s not shared like with Gouraud shading.
With indexed primitives like the glDrawElements you can reuse the vertices of the previous row for better performance.