I know your past the very beginning, but did you modify your starting decks? Even the starting cards can be improved with better starting cards (For example some chars have a short sword which is just weaker than a long sword that you can get at the start)
How are you doing your skill feats? I find the first early ones are best used to improve your combat stat. As for power feats it depends, but I like to get anyone with 4 cards up to a 5 card hand limit, and go from there.
Some advice for who you are using:
Fighter- If you have multiple weapons in your hand, don't be afraid to discard them during a combat check. The fighter recharges them, so you don't lose them and it allows you to cycle your deck quicker. You want to make sure you keep one in hand however.
Paladin- Here power to discard a card to add 1d6 is one of the best abilities in the game. Don't be afraid to use it often, as she has a lot of blessings, and they get recharged. If you are running low on time, using her crusade ability (Examine the top card, put on bottom if boon) is a good way to catch up on time.
Cleric- Cure spells are better than her power because her heal power cost you a turn (No free explore). That being said it's still better than dying. I try to balance her with some attack spells, and some cures.
Mage- There isn't a mage, but I'm going to guess you mean Wizard. You want to take him to places that have spells, so he can take advantage of his multiple explores. Most of his spells should be attack spells, and maybe a detect magic (Unless you get augury which is a great exploration spell) The wizard is the only person with a high int score, so going to locations with a lot of items is good as well since if there are lots of potions he can get them.
Rogue- Don't be afraid to put her at dangerous locations, she can evade almost every card (There are only a few that you can't evade) Shes great in spots with a lot of barriers since most require dex and that's her specalitly. Keep her by herself, and use backstab every chance you get (another great cycling option).