For a really good example of battles requiring strategy, I suggest you play the "The Way" series by Lun. There is no leveling up and every battle can become like a boss battle if you just hammer away at the enter key to use the attack command. But if you're too lazy to try that game out, here's some pointers.
1) Have enemies utilize attributes, and make a variety of weapons and items that vary in strength but have different attributes associated with them. For example, don't Final Fantasy it and have a straight shot of weapons getting stronger and making previous weapons useless until you get an Ultimate Weapon of ZOMFGLOLZ Uberness. That's overdone way too much.
2) For projectile based weapons, script a skill that requires you to load the weapon first, and if the weapon isn't loaded, have the attack be a weaker 'unarmed' attack instead. Example: Character with bow wants to attack an enemy, but bow isn't loaded, so he hits the enemy with his fists. Furthermore, make weapons require skill points or an equivalent to use.
3) Make the enemy parties as specialized as your party usually is. Create 'healer' enemies, 'attacker' enemies, 'wizard' enemies, etc., and integrate them into monster parties so that you have to eliminate them in a certain order so that you don't, um, die.