'd rather use images or textures but hey ... when you're desperate I'll make do with rectangular colors if I have to I have actually tried solving the problem with vertex rectangles before and they gave about the same speed as gldrawpixels (too slow).
Using vertex colors instead of textures will reduce the number of gl calls. Since you only need to transmit it once per quad, or less if it don't change. Won't give you a huge improvement.
Or generate a texture that is uploaded once per frame and drawn with one quad that covers the screen.
If I understand you correctly - there would need to be several million combinations of screen texture depending on where the 2 tiles are within the grid so this couldn't be an option.
Sorry, I wasn't clear. I was thinking that the texture is an image of the grid, where one pixel represents one tile. It's got the same limitation as using vertex colors, the tiles can only have a single color. You generate this texture in software and transmit a new one every frame. This will only be a 128x128 texture so it won't be to slow. Then you scale it up to fit the screen using a textured quad. On a related note, how fast is it to draw a single image with the size of the screen using using glDrawPixels?
2) Use Triangle strips or quad strips.
Don't know much about these ... do you think these would give me more speed than drawing vertex rectangles
It would be slightly faster because of less gl calls. See "OpenGL Geometric Drawing Primitives" in the Red Book.
In the end I think you'll have to be creative to find a method that will be fast enough.