Yeah, it would be totally possible. Basically it would be like taking a multiplayer map and then removing the victory conditions.
At one point we were going to make that Multiplayer Tutorial useful where the computer would send waves of combat units at your base, and make them progressively harder.
I think another idea for a colony game would be something where you have to 'survive for 30 minutes', and units are massed and sent to your base. However, in this version you could tweak the settings, perhaps upload or download 'settings files' to make the mission as easy or as hard as you wanted.
As for a 'full on' computer opponent, well, no one has written an AI that would perform really well yet (any 'AI' that has been made is basically a list of commands, for example, at mark 500 create 2 lynxes, or on approaching the AI base, move 2 lynxes to defend, etc)
I think Eddy might have one in the works.