A general MegaTen example: Petrify and Charm. No, seriously. Charm can be obtained very early in pretty much every game, and doubles as one of the best ways to deal with bad Elemental Rock-Paper-Scissors matchups you're bound to have, a way to deal with Goddamned Bats and a way to keep your party healed with low cost and, though rare, can also works on minor bosses. Petrify, on the other hand, kills pretty much everything non-boss, barring some rare occasions, with surprisingly high accuracy, even though it takes longer to get.
The original Shin Megami Tensei plays around with this trope a bit. Early on, you can create a unique, high-level Cerberus by fusing your pet dog with a demon, in one of the precious few exceptions to the rule where you cannot create or recruit a demon of a higher level than yourself. This lets you plow your way through many of the game's early enemies. About halfway through the game's first act, however, it leaves your party. After you and your comrades are teleported to the demon world just before the nukes fall, you get a chance to reunite with the very same Cerberus, which also makes him a Disc Two Nuke.
In the first town's Casino, you can purchase the Cat 'O Ninetails, an absurdly powerful melee weapon for female characters, for 5000 coins. That price might seem a bit prohibitive at first, but it's really not that hard to win that much with the slots. The only real limitation is that you must be of the Neutral alignment to equip it.
Using Demon Fusions with a 'human' demon (ie any 'Gaean' or 'Messaian' type creatures) as a component is a bit of a wildcard. It could result in nothing spectacular, but could also land you monsters of much higher level that, amazingly, completely ignores any level restrictions. With diligence, you could end up with the likes of Metatron and Kali before you even leave the first town.
The first Persona has Phaleg, a level 18 Persona that nullifies magic and has a powerful attack spell and Mediarama (the first Persona to have it; the rest are at level 29 and up). Not only is it absurdly easy to obtain, you can fuse it at a point where it can literally one-hit just about anything, and it remains useful even in the endgame due to its low SP cost.
In the Updated Re-releasePersona 3: FES, you can now indulge in Item Crafting at the Shinshoudo Antique Shop. The process is simple: you must forge a persona you have in your inventory to a "blank" weapon. With a bit of Money Grinding, and use of the Old Save Bonus feature to bring back one's persona compendium from the original game, one can buy back a high-level persona and fuse it to any blank weapon resulting in a weapon you probably wouldn't get for at least 70% into the game. For more fun and potential game breakage, forging certain personae results in an Infinity +1 Sword.
Fusing the right 3 Persona (Pixie and Nekomata then the result with an angel) early on can give you a Lilim with the 4 main elementsnote In this game, hitting an enemies weakness gives you an extra turn once per round by level 8. This lasts more than long enough for the next quad elemental persona (Pale Raider) which lasts till the right skills are accessible for specialists.
A similar recipe exists to create a 4-element Yomotsu Shikome a Lv. 9 Hermit persona. It's slightly better than Lilim because Shikome has no weakness and is resistant to Darkness/Mudo.
You can do a similar trick in Persona 4. New Game+ lets you carry over your money and any registered personas. As soon as the compendium is available, you can just buy a high-powered persona such as Ardha, Lucifer, Satan, Metatron, Yoshitsune, etc. and bulldoze through dungeons in at least one day.
There's also the "Victory Cry Kaiwan" trick. Kaiwan is a Lv. 24 Star arcana persona who starts with Tetrakarn. While it is a useful spell because it will reflect any Phys-based attack (except almighty) once, the true beauty of it comes when you fuse the persona on a day where the Fusion Forecast gives the "skill change" bonus. When it is fused with the least amount of passed-on skills, there's a random chance of Tetrakarn morphing into Victory Cry (full HP/SP restore after winning a battle). If Kaiwan gets Victory Cry, he makes great fusion fodder for passing the skill to other personas. While Victory Cry is the most desirable skill, it's also possible to get any number of high level abilities like this, such as Repel Physical.
As early as the first dungeon, you can obtain the Persona Slime, who learns the skill "Resist Physical", which is incredibly useful against the early enemies who don't use magic as often. On top of that, in Persona 4 Golden, you can pick the Magician card during Shuffle Time to turn it into "Null Physical", making you completely immune to physical attacks, which is extremely useful during the whole game. While Slime is a weak Persona in terms of stats and attacks, the Resist/Null Physical skill can then be passed down through fusion, making it easy to acquire an army of powerful, physical-immune Personas right at the start of the game.
Agathion is one of the first personas you'll receive, being handed to you for free once you have the ability to equip sub personas. What makes him so good is the fact that it starts with Hama, and almost every single enemy in the first dungeon is weak to it, as well as a few annoying enemies in the second. To boot, once Agathion has been outstripped by stronger personas, it can be fused into several incredibly useful personas AND pass them Hama.
Turdak is a persona earned for completing a side quest in the second dungeon. At first it can be underwhelming as it is meant to use the various 'Link' skills, but the nuke part comes from the fact that it can learn 'Shinkuuha,' a skill that's a gamebreaker in and of itself, and the passive skill 'Heroic Gemini,' which gives about a 20% to use a skill twice with no extra HP/MP cost. This persona is obtained at around level 20, but can easily be used up to around the FOURTH dungeon, which is around level 50!
Raidou Kuzunoha VS King Abaddon features Fiend battles. They are quite tough as per usual for the series as they start hounding you as early as Episode Three. However, with a little patience and demon setup, you can kill the White Rider (and Red Rider if you're lucky) and unlock it for fusion. What makes this so great is that Fiends do not have the level restriction as most other demons—all you need is to have defeated the Fiend just once, have the proper gems (which can be acquired by bribing demons) and the moon phase to be New Moon. If you create the Rider, he'll be about 40+ levels higher than Raidou, have a boatload of resistances and can be augmented with Full Moon Mitama fusion. With this demon(s) on Raidou's side, they can pretty much curbstomp the next two Episodes or so. This can also be done when fusing Magatsu/Evil-type demons (any moonphase except new moon), and for those you don't even have to kill them to unlock. The system can be further exploited by the fact that you cannot have the same demon twice, Fiend and Magatsu/Evil fusions are no exception, if you have the demon that you would get from the gems, you simply get the one lower, unless there isn't any in which case you get one HIGHER, with enough time and saving you could easily get a level 31 and a level 33 evil demon from the moment you are able to fuse.
This is a later example, but Shin Megami Tensei: Strange Journey has Black Frost and Frost Ace, both of which have no weakness and spells that demons of their level shouldn't have; namely, third-tier ice attacks and a Total Party Kill. You can get them both as early as Delphinus if your level's high enough; having both of them only requires you to be at level 34 and having 5 specific demons in your party, which the game is generous enough to tell you.
Unlocking the fusion for Frost Ace, which can be done a little earlier, gives you an extra Disc-One Nuke in the form of the Frost Cannon, a gun that comes with three spells; Bufudyne, Mazionga and Garudyne, all three of which are notably stronger than what other guns available to you at this point come with.
In Devil Survivor 2, you fight against Botis, who has the Ziodyne spell (strong electric damage against one enemy), relatively early in the game. If you use skill crack to get it, it will be the only -Dyne level spell you have for a long time.
Early on in Nocturne the Demi-fiend can learn the spell "Fog Breath" from one of his starting Magatamas. It's two castings of Sukunda (lowers accuracy and evasion) in one. Despite the MP cost it will your save your life, as enemies will lose turns if their attacks miss. It continues to be useful all the way until Demi-fiend and his familiars can learn Debilitate.
Focus also qualifies, being learnt as early as level 23. It's a cheap spell that amplifies the user's next physical attack by over 2 times. It never leaves the skill set of physical builds, especially for those going for the True Demon ending where they also attain Pierce to bypass most physical resistances.
Treasure Demons come jam-packed with useful skills that make them great fusion fodder, and will be recruited without demands if you knock them down. The first one, Regent, is a fixed encounter in the second Palace designed to serve as a tutorial for how they work, and cannot be missed. Said Treasure Demon comes with first-tier area-hitting spells for all eight magic elements, which is great if you're missing elemental coverage. Once the Gallows are unlocked, the Treasure Demons become invaluable for imparting bountiful amounts of experience to power-level your Personas in exchange for some money, on top of imparting a random skill they possess.
Swift Strike is available as early as level 19 for Joker, but causing a guaranteed 3-4 light hits to all foes is a lot more powerful that it sounds. Don't be surprised if you find yourself keeping this skill on most new Persona you upgrade from.
Shiki-Ouji is a level 21 Persona that Nulls Phys/Gun/Curse skills, an absurd level of resistance for that early in the game. Given the amount of Phys skills alone you come across, Shiki-Ouji more than makes up for his level in sheer usefulness right out the gate.
Itemizing Ame-no-Uzume (which the player would no doubt end up fusing if they're working on the Strength Confidant) will create Senryou Yakusha, a katana for Yusuke that gives an impressive +5 Strength bonus. Even if its power or accuracy will get overshadowed later on, this stat boost continues to be useful into the late- or endgame, where the player would be using his physical skills more than his basic attack.
As expected by their Downloadable Content status, the Legacy Personas (Orpheus, Izanagi, Thanatos, Kaguya, Magatsu Izanagi, Messiah, Ariadne, Tsukiyomi, Asterius) are overpowered for how early you get them in the game — you absolutely destroy the < level 10 enemies with the level 20-81 Personas, even on Hard or Merciless difficulty. What really drives them into this territory however isn't just their strength, it's that the first summoning of any of them (even the lvl 80 personas) is entirely FREE of charge. Any summons after this should you use them in a fusion must be paid for of course, but still a free courtesy summon is insane to ignore.