KahlessNestor
Adventurer
Since this is a thing you're currently mulling over, consider the following:
Let's say I've signed up for your campaign, and that you haven't ruled out any specific race or class options--and, if you'll allow it, starting at 4th level (I think it unlikely that I'd want to join a low-level 5e campaign again, it's too meatgrinder-y). I tell you, openly and frankly, that I've had an idea that really struck my fancy, a character that is Proficient in all skills (eventually), but that I'll need to multiclass (and take feats) to do it. The character, we'll call her Rhiannon (one of my favorite female names), grew up as the prodigy daughter of a moderately well-off human family, one that could afford to send her to an actually good school (as much to keep her occupied and out of their hair as to indulge her abilities). So she was educated in all the formal subjects, including music and magic--mechanically, she's a Variant Human Bard, who took up the College of Lore at 3rd level. Variant Human grants 1 bonus skill, plus 2 from whatever her Background is (I'm partial to Academy Graduate, a homebrew BG from the ENWorld forums); Bard naturally gives you any 3 skills, and Lore gives you an additional 3 skills, for a running total of 9 skills, and two of them have Expertise. Variant Human also grants a bonus feat--which, in this case, is Skilled, granting a further 3 skills for a running total of 12 proficient skills at 3rd level.
During or after her formal education, Rhiannon to a realization: she doesn't just hunger for knowledge. She feels a genuine transcendent element to it; she reveres it in some sense. Moved by this epiphanic experience, that Knowledge is an ineffable transcendence rather than just a feature one can possess or lack, she attempts to join the formal clergy of the/a deity of knowledge, and is thus Bard(Lore) 3/Cleric(Knowledge) 1. Though the addition of a little bit more martial skill is welcome (Medium armor and Shields), it is the additional education that she really longs for, giving her an additional 2 languages and 2 skills (probably Religion and Nature, running total 14) plus effectively getting Expertise with them (her proficiency bonus is doubled for those skills). However, she finds the clergy stuffy and rule-obsessed: they really don't care all that much about learning ALL there is to learn, and rather about preserving and documenting and cataloging, which she considers the least interesting aspect of Knowledge--particularly when they turn a blind eye to both useful and fascinating skills like...say...lockpicking!
So she leaves the Church, though not the faith, and strikes out on her own as an adventurer-for-hire (aka, campaign begins). The plan for the character, at that point, is to have her further indulge her hunger for knowledge of a less-savory variety, and thus have her take a level of Rogue at character level 5--dabbling just enough in the shadowy arts to become an expert on the book-learning side of things. (If you've played Morrowind, Oblivion, or Skyrim, think of the character Yana from the Lockpicking skill book The Locked Room--the "professional amateur," who delights in learning all the esoterica of lockpicking for the joy of learning, not the function.) Mechanically, this gives her a skill from the Thief list (probably Stealth; total 15), proficiency with Lockpicks (which, while technically a Tool proficiency, is practically a Skill of its own), and Expertise proper with a further two skills (for a running total of six, or five+Thieves' Tools), plus Thieves' Cant which complements her broad spectrum of known languages (Common, 1 from Human, 1 from BG, 2 from Knowledge Domain).
Should the character last to 6th level or beyond, she would return to the arts she had left: because really, the only secrets left to be revealed are those of a purely magical nature. She lacks only 3 out of the 18 skills; a second application of the Skilled feat solves that problem, though technically the feat doesn't specifically say it can be taken twice. By continuing as a Bard, Rhiannon will gain another four Expertise skills, for a grand total of 8 out of 18 Expertise'd skills. She speaks/writes five languages and Thieves' Cant; she has proficiency with both Thieves' Tools and a single game set (probably a chess-type game, though if "cards" in general is allowed that might work too), as well as three instruments. And, finally, whenever she makes an ability check that doesn't benefit from proficiency--which, now, only means Tools she's not proficient with and any checks that can't normally get proficiency e.g. Initiative--she still gets half proficiency because of Jack of All Trades (as all level 2+ Bards would).
Or, if that was TL;DR:
Narratively start as the precocious daughter of a well-off family who voraciously consumed knowledge in her formal education, found faith in Knowledge itself but disliked the strictures of the formal Church, so she is off to pursue the things she couldn't learn properly in the temple or the library. Once she's drunk her fill of the larcenous lifestyle, the higher mysteries of magic call to her, mysteries spanned through their whole breadth by the disciplines she learned back in school. She'll face every challenge with a wry smile, a sprightly tune...and a polymath's brain.
Mechanically start as Bard(Lore) 3/Cleric(Knowledge) 1; take 1 level Rogue; resume Bard for remainder of levels.
So now the question is: is this me being "powergamey" or in it only for the "overpowered" abilities, or is it me being interested in a solid story about a character with a clear motivation behind her actions? Is it, perhaps, both things? Would you allow me to do this?
---
On a separate subject: don't forget that Paladins are no longer specifically servants of deities. Their power may easily come from conviction alone, from thoroughly believing in an ideal rather than being purely servants-in-shiny-metal (or shiny leather, since Dex is a valid stat for Paladins now). As you've noted, an Oath of the Ancients Paladin can have an explainable link to the Fey; I would similarly argue that the Oath of Vengeance can be linked to either of the other two Warlock Patrons. I mean, it says right in the description that, "To these paladins--sometimes called avengers or dark knights--their own purity is not as important as delivering justice." That bespeaks of a character willing to go to great lengths to see a particular outcome, even if it means sullying themselves with dark deeds and dread consequences, which is very much like what a Fiend Pact could involve. The temptation to make a rash deal for the power to defeat a foe when all seems lost can be perilously great--particularly when your powers do in fact revolve around defeating such foes!
1. Yes, I would allow your skill monkey character. Youhave good thought out story.
2. The whole "strength of conviction /oath" for paladins in the current edition doesn't fly with me. It doesn't make sense. Clerics and paladins have gods. Pethaps if I were playing Star Wars and ising the Force. Possibly your idea might work for an evil deity, but not the good or even neutral ones.
