Your characters probably have weak genes/max levels. You need to breed them to improve those or find better ones in the wild/drug them up with potions. A character with 0-1 genes in strength and a max level of 5-6 might have less strength at max level than a character with 5 genes in strength at level 1. Genes and max level really matter, the more levels they have, the more stat ups they get. You should always be trying to raise the max level of characters when breeding. For example I have two Lymean, one at level 10 (max) and one at level 13 (max) with the same magic gene level of 5 stat. The level 13 has has 13 total magic and the level 10 has 10. I think there's a bit of randomness to it, but it's still pretty huge.
The game is balanced in a way that you need to constantly be improving your roster with improved genes, gene traits, and skills, or you'll fall behind. It's not really feasible to try to stick with the same roster for very long, even though you can raise your starter's max levels now, their genes/traits will likely still suck (Until Gene Adaptor anyways). Generally the idea is you want to max a character's level in a portal/arena or whatever, immediately breed them, then ditch them to the library/fusion/tavern when you get a good egg result. Make sure to try to throw in some good traits like Strong, Resilient, Arcane, Fast, Intelligent, Prodigy, etc, etc. You usually don't want to be taking max level characters into combat as a good rule, as that's just wasting exp somebody else could be using, the only exception being for special portals where you need strong fighters.
On the MC strength bit, that depends on what character you're playing as. Creation isn't really meant to do melee damage, though I guess you could build her for it. Evolution you need to upgrade her stats with the Change menu. The ones that improve her genes don't apply to her stats, they only help with breeding. Make sure you get the ones that improve your base stats. Centaurs have a lot of strength bonuses for Evolution for example. Bang lots of Centaur races lol.