Savage Worlds can work great for fantasy, so long as you're not expecting it to work exactly like D&D. The characters are competent from the start and powerful in an over the top or "pulp" sort of way. 1) Fast and brutal combat. Combat runs at least as fast as any game I'm familiar with apart from something extremely bare bones like OD&D or maybe Risus. The game's tag line is Fast! Furious! Fun! and it does it's part. If you give your players access to something like this combat cheat sheet , that will help smooth things along. How brutal the combat is can also be controlled by how frequently you award out bennies (fate points) to your players - so you'll always have a way of adjusting how things go on the fly. Sneaking up on people and trying a coup de grace is called "getting the drop" in Savage Worlds and there's rules for that. 2) Character progression with limited power creep. Given that a PC's biggest edge is the wild die - that they get from the beginning - there isn't a huge dramatic shift in capabilities at thresholds. Characters will get more powerful as they gain experience, but not to game breaking levels suddenly. However, with how the exploding dice work, your big and scary monster can be one-shotted by the players on occasion. Conversely, your players can be one-shotted by the big and scary monster on a good roll. Unless each has a stack of bennies to play with, that is. 3) Fairly flexible character customization from the start. You're good here. One common complaint is that characters can feel the same at character creation. I'd stress to your players that the selection of edges is the key way to differentiate characters and if they play their selected flaws to the hilt everything will click into place. Some disadvantages: You're going to have to either buy into a setting or the Fantasy Companion in order to get a fleshed out magic system. The one in the Explorer's Edition is a kind of skeleton that you hang different trappings on each type of spell. It works, but might be a little lacking right out of the gate. Also, players have to get how the bennie economy works and how the various "tricks" work in combat before the game starts feeling like it's own thing. Just trading blows with the enemy is going to feel a little bland. If you're still looking for alternatives, something like Mongoose's Legend (as mentioned above) could also work - it's only a buck to check out and see. If that is more in the vein of what you're looking for, you can expand into things like RuneQuest or OpenQuest, but Legend is a solid system in its own right. I'd also recommend Barbarians of Lemuria as a more simple yet powerful system that meets your needs as well.
