Gladiators do not start with a shield, fighters do. A very popular combo was MDFi of Okawaru. You might like Makhleb a lot he offers good ultility to a melee fighter and is a lot of fun to play. He will give you a piety free "spell" (minor destruction) at **, and he also gives you healing when you kill, and can summon (usually but depending on your invocations skill) friendly demons to help you out. MDAK is also a solid combo, if you want to worship Lugonu, you'll want to do it from the start as an abyssal knight as her alter only spawns in the abyss (unless you get a "corrupted temple" by chance, but it is only guaranteed in the abyss) Elyvilon is also a very powerful option.
Personally I have not played Makhleb a lot but I have heard great things about him, people seem to love playing him. I'd give that a go. I am quite partial to abyssal knights though
EDIT: Trog's trog. Pretty straight forward strong god but no casting. He will easily last you through a 3 rune game. Zin is meh. Fun, but I wouldn't start Zin in stable. He gets buffed in trunk though and is more fun, but you won't get the god zin
andmountain dwarfs. But then just fill in minotaur or hill orc in the place of mountain dwarf and you will be fine.