Since these two classes work very well together you can go in pretty much any direction and it will be powerful.
I would not use an Oracle of Life thought since the Paladin's Lay on Hands ability and your own spells will give you a good source of healing already and a different mystery offers more versatility.
The Lore Mystery for example would give you access to the SideStep secret allowing you to substitute Dex with Cha for Reflex and AC.
The Lore mystery will make you a very knowledgeable character, so you can play the role of a sage.
Using your knowledge and spells to support the group in and out of battle and using healing to keep them from dying.
Heavens has some really nice bonus spells. Might be worth looking into.
An oath of vengeance paladin and a life oracle would work pretty well together. The oath of vengeance does not get channel positive energy, and will be using his lay on hands to get extra smite as well as heal himself. This means that there is not going to be a lot left over for the rest of the party. This will allow you to go full out offensive with the paladin and then heal the party afterwards.
Life oracle also gets most of the important condition removal spell from his mystery so he does not have to worry about those. The paladin especially at low level is going to have a hard time fulfilling the role of a healer, which means you are going to be using your oracle spells to supplement that. With a life oracle you can use your channel energy to do a lot of the heavy lifting for healing freeing up your spells to be used for other things.
If you aren't planning on being a mounted paladin, I suggest oracle of battle. Yes it's boring, but you get surprising charge, which allows you to move your speed as an immediate action.
Now if you're a mounted paladin, don't forget the paladin mount is one of the strongest companions around. Try and get some "self" oracle spells and throw them on your horse. Righteous Might sticks out to me right now. If you could get alter self or something of the sort, your horse could theoretically be a humanoid fighter with you.
I don't understand why people are so infatuated with the paladin/oracle, the revelations are barely worth it unless you're planning on leveling more oracle then paladin.
If you want to be more of a Combat/Healer, be a Paladin/Warpriest,
Warpriest compliments everything that a Paladin is
Pal 10/War 10
Full BAB with Sacred Weapon
Divine Bond with a Mount
and Sacred Weapon
and Sacred Armor
Blessings (Magic & Healing are my favorite)
Aura of Law & Good
Detect Evil
Lay on Hands
Fervor: As a Swift Action, expend one use to cast a prepared spell on self.
Smite Evil and Fervor
Channel Energy x2 (two ways to use it)
Spontanous Casting
and much much more.
You basically become a conduit of holy might.
Justin Sane: It's hardly an offset to the amount of advantages you receive in return compared to the Oracle.
If you're planning on the primary tactic of Life Linking your party and topping up your HP when needed with Swift Action Lay on Hands then Fey Foundling, Greater Mercy and Extra Lay on Hands are fairly necessary. This doesn't stop you from smacking things with a Greatsword either, so Power Attack is definitely useful.
The Life Oracle/Paladin combo is great when it's a 4 level dip of Oracle, you might get a lot more mileage out of another Mystery with full Gestalt progression. Battle, Metal, Ancestor and a couple of others offer tricks that might give better value as a Gestalt. You can already pick up all the Life mystery spells as normal choices and the Life revelations aren't the best.
I do not recommend the Lore's Sidestep Secret with Paladin levels. If I recall correctly, there's a post from James Jacobs around that says you can't add the same stat to a roll twice, so SS replacing dex and Divine Grace adding Cha to reflex would be a bit wasted, only addding Cha once with no dex.
However, the Nature mystery has Nature's Whispers which replaces dex to ac and cmd with Cha.
Nature Mystery is pretty cool, and allows you to have a (slightly weaker) bonded mount and still choose a divine bond weapon as well as the AC bonus. I could see a Paladin of Erastil/Nature Oracle working from a roleplay point of view as well. While the spell list you get from it is a bit rubbish several of the Revelations are good. Erosion Touch for melee touch sunders and Natural Divination for skill and initiative check bonuses.