I can only fully describe deity, as that is the only level I've spent much time playing. I can also give a brief description of monarch.
Deity:
-----
The AI is very powerful early on, expect to be swamped with their units if you get into a war early on. They get 4 free units per city (I think) and get 2 settlers and several free units to start off with. Be prepared for an early uphill struggle, usually I try to get an early war going and invade a nearby AI, it's the only easy way of doing things (early war should start before 1000bc, if possible). After you manage to take out a couple civs in this way (leave them with a few cities and harsh peace treaties which provide you with plenty of techs and cash) you should be about equal with the AIs. This should occur by the time you reach the end of the middle ages, tech wise. Once your on equal terms, it's a lot less difficult. Try to stay at peace and build up. The cash and tech from your vassals, plus the money and tech from your rapidly developing cities should allow you to compete. If you fail in your early war, expect to be mediocre all game. Basically the only difference between deity and the other levels is the number of units and techs the AI gets early on - AI strategies are the same, but the brute force they can employ against you can make them challenging at times.
Monarch:
---------
The pace on monarch is a little faster than regent - expect the AI to take a couple tech lead early on, and to have a slight lead in unit count, but you should easily be able to catch up if you develop your empire properly. Early conquest is probably less of a good idea on this level, perhaps conquering one civ to provide you extra room to expand would be ok. Otherwise, I'd go perfectionist and expand up until the middle ages. Then go conquer. The reason you wait on this level is because the AI has less bonuses than deity, and so conquering wouldn't be worth it as they will have less cities and many less techs. By the early middle ages you should have a tech lead if you've been building your cities up economically. This level on the whole, along with regent, the only other level I have played, has a much more relaxed pace than deity. Expect to have more freedom in choices (go conquer, or go perfectionist, etc. all your choice because all will work), and expect the AI to be much less dangerous early on. Builder strategies actually work well on this level too, which can provide for a refreshing change (my only OCC civ3 game was a cultural victory on monarch level).