First piece of advice: Don't come up with a rule and blindly follow it.
Second piece of advice: Generally, bump enemy HP from average to maximum; this is a simple change that helps.
The other two big things are in fact the Advanced Simple template and increasing the number of enemies, as mentioned above. And, again, as mentioned, for solo fights, add some minions or lieutenants.
Be very cautious about the Advanced Simple template at low levels; basically at low level, there's less room for optimization to have made a big difference, so adding +2 to hit and +4 to AC on enemies makes a big difference. I almost killed my party's paladin very early because I underestimated how dangerous the template made some enemies.
As you get a feel for the party, you'll get a feel for adjusting the encounters as appropriate to your party.
Also, don't be afraid to make tweaks mid-encounter. If the party is having too much trouble, invent an explanation and weaken the enemies. If the party is blowing through too easily, have reinforcements come in, or insert another random encounter to make them expend more resources.
The reinforcements strategy is also a nice way to avoid having your increased enemy count get wiped out by one fireball, and to deal with dungeons where there are a bunch of adjacent rooms with similar enemies; it keeps you from doing many repetitive small combats, avoids overwhelming the party with a huge mass of foes, and means you don't need to explain why these guys just hung around in their room while the party killed their friends next door.