X-COM, Enemy Unknown? The remake on consoles and PC? NO magic in that unless you want to count the "Psychic" abilities you can get later on. It works on the same principles you're describing. Weapons, movement, and terrain matter. Skills are mostly in the form of passives with a few actual "special attacks" that have cooldowns (which can take as many as 5 turns).
The problem with it?
To keep combat interesting, the game ends up throwing different enemies at you in different groups so that no one strategy really applies to all situations. This becomes a major problem because sooner or later, the player has figured out all the strategies that are going to be thrown at him. Even without magic and states like "Poison enemies", the gameplay gets somewhat repetitive. There's only so many things you can do. Go to High Defense Terrain, bunker up, fire your guns from there until the character dies or you win. It's more advantageous in most missions in that game to simply hunker down in cover with good firing lines and then wait until Turn 20 when the AI will come find you instead. Why should I ever have to endanger my units to dig out the enemy? Especially when doing so may even cost me the mission.
About halfway through that game, I actually found a super amazing strategy that beat anything else I had been doing up to that point. I had figured out that Shotguns are basically the best thing you can arm yourself with, and kitting out your characters to maximize effectiveness with them only increases your deadliness. What did that mean? It means I had a woman running the entire map, dashing from location to location (sometimes with or without cover) and shotgunning everything in the face for one shot kills or nearly one shot kills. Before the end of the game, she'd racked up something like 540 kills compared to everyone else's 100 some odd kills.
Without proper AI or without skills that a player would have to consider, there's really no incentive to not just grab the most effective unit or team and use only that forever and ever until the end of time. In my game, the only thing I ever really worried about was the "Sectopod", which had like 2 turns to your one (AOE Missiles which covered a huge area and ignored cover and a huge beam weapon that usually one shot any character that got hit) or the Ethereal which could cast "Mind Control" on me. The best solution to either of these? Kill those enemies as fast as possible to limit their damage or free comrades from enemy control. No other ability in the game the enemies employed was ever as useful against me.
If nothing else, I suggest a few "situational" skills or bonuses to character/class that could help you out on certain terrain squares or in some situations. Things like "The Thief cannot be flanked" could be useful, or "The Ranger gains +2 ATK and +5 DEF on a Forest Tile" might be plenty to keep players interested.
You know what keeps Chess interesting? Every unit moves differently and uniquely. Losing those units limits your mobility and ability to attack. If you could manage to make combat in your game the same way, it would remain interesting throughout. Especially if the enemy gets similar unique units and abilities that make you have to plan out several moves in advance.
However, if all you're doing is "units can only move so many squares, have different weapons/attacks, and terrain can be useful", players will get bored with it fairly quickly. Combat is made interesting through variety. Strategy is made interesting through possibilities. If you are going to cut out skills and magic, then you need to replace those with something that serves the same purpose (namely adding strategy beyond where you're standing).
