My recommendation is to have on one set, dual swords (dual gladius probably, for the crit). On the other set, have a shield and blunt weapon (mace or bipennis, your dex is probably not high enough to reach 80% balance with a warhammer yet).
Lance is a good option, but it takes some getting used to. The reach is weird, so you'll have to practice (however, Lion Claw Lances are going down in price, and those are the best lances in game right now, so grab one up when you can).
For Paladin skills, do Spirit of Order first. It's a pretty good priority. Reference the mabinogi world wiki for more info on it lol.
Wiki Home - Mabinogi World Wiki