First of all, you only need a certain amount of troops to garrison a city. its normally somewhere around the 20-40 mark, but can go high for some huge cities. If you have not enough food though the town will revolt regardless of how many troops. So make sure you don't have too many soldiers in the town. They will eat food and are not doing anything useful. Food issues definately sound like your main problem. Also, generals do not increase in the sandbox mode. If they are apperaing in towns it is because they have been defeated in the field and are re-spawning back in their homecity.
The best startegy is to expand slowly and to garrison each town with cheap units like spearmen from your home territories. Try and get the minimum amount of soldiers that you need. Also, Sparta is maybe not the easiest nation to play. Have you tried playing the Philip of Macedon campaign? It is easier I think because of the stronger Phalanx units and because there are so many missions that give you plus money and other bonuses.