You could go the route some of the old BBS games took. Give them so many actions per unit of real-time. This could be 100 per day, or 4 per hour, or anything that makes since for your game. You might also want to cap these stored actions up a maximum of a few days worth. That way someone who plays a lot gets a little bit of an advantage, but someone who plays every couple of days isn't hurt too much.
For armies/battles, they could be inherently slow. If I send my army to attack you on Monday. They're in transit on Tuesday (so you have 1 day to react to it) And then the battle plays itself out on Wednesday.