This might not be as much of a problem as you think. Why? Because munchkining, minmaxing, optimising, whatever you want to call it - is severely limited in 5e. The main techniques for it in previous editions of D&D involved things which are significantly less effective in 5e.
Multiclassing has been crippled by the all-important ability score increases/feats being a feature of class advancement instead of character advancement. There is currently a limited selection of classes and feats, so taking advantage of obscure classes, prestige classes, variants, and feats is no longer an option.
D&D 5e also introduces the concept of 'bounded accuracy'; see here for a good explanation of this idea. There is only so much it's possible to do to optimise a character in 5e, and the gap between an optimised character and an unoptimised one will be fairly small.
Your players will still spend time optimising their characters, of course, but that's not necessarily a bad thing. If a player hasn't spent any time on their character, that's a sign that they may not be particularly invested in them.
As far as creating playable characters with reasonable backstories goes, this is a great opportunity to use their munchkin-ness against them. They're going to want to choose a certain background for the proficiencies it offers - make them justify it. You want to be a Sailor who became an adventuring Wizard with a single level in Cleric? That's fine, but you'd better have a damn good explanation for it.
And using their munchkin-ness against them is a great technique to make them roleplay, too. When they create their characters, they'll choose a bond, a flaw, an ideal, and a trait. Let them know that you're happy to hand out inspiration (which is incredibly powerful - advantage to a roll of your choice? Sweet damn, who wouldn't want that?) if they play their character. Positive incentives have been used to motivate people to do what the motivator wants for years, because it works.
Quick bit of backup for all this - I'm DM-ing 5e for a group consisting of 3 munchkins and 2 roleplayers. One of the munchkins is so bad he walked into a core-only 3.5 game and insisted on creating an Artificer. And you know what? He's playing a single-classed Fighter, roleplaying as much or more than the roleplayers, and (as far as I can tell) having a great time doing it. (Oh, and he also has by far the most extensive backstory, he really got into it when he was choosing his background options.)
Outsource it to your Players
I find this happens in games where there is an unspoken agreement that the DM is going to in charge of (everything) about the world, and the players are going to be in charge of their characters, and that's it. That is, historically, the way games have worked. But it isn't the only way they can work.
You could for example, sit down with your players, and talk about what kind of game you'd like to play, what kind of challenges they'd like to face, and ask them how they'd like to balance those interests. You can bring up these issues, and ask them for solutions. If nothing else, it'll prepare their minds for there being times in game when they won't get to do their favorite thing.
Build the Game Together
There are tools for building a game. Depends on how deep you want to go. If you're comfortable taking a lot of input from players on how the world is going to be, you could use Sparks For Fate Core. It's built to use with the Fate RPG, but there is absolutely no reason, if you understand Fate as a game, that it can't be used to build worlds for other games. You don't even have to allow Aspects to mechanically influence the game, just use Sparks as a worldbuilding tool.
This will likely make your players more invested in the world, and so they'll be more interested in the roleplaying opportunities you present. The GM still has ultimate say over what happens in the game, but the players get to say what they're interested in. It might depend on your GM style, and whether you're comfortable adapting to player input into the setting. For me, it actually takes work off of me to not have to come up with things I think will be interesting to the players. I can simply riff off of the things they've already told me they're interested in.
Taking one step back from the setting/game design of Sparks, you may find The Same Page Tool useful. This is a series of questions that prompts the players and the GM to talk about their expectations. As mentioned before, a lot of things can be unspoken in games because of a misguided expectation of "building suspense" or "preserving mystery" for the players. I'm here to tell you that you can talk about the meta game, and still have the in-game moments be fun and surprising. Throw out the unspoken rule that the first rule of the game is we don't talk about the game.
Rolemaster Zodiac
Rolemaster is an old school game that had a section called Gamemaster Law, which is useful to anyone who plays RPGs, whether or not they play Rolemaster (I never have). Like the astrological Zodiac, it categorizes players into different types according to their proclivities while playing, so that you as the GM can better organize them and deal with their needs and potential problem areas.
Try to remember that humans don't always fall neatly into stereotypes, but the ability to say "Oh, Kyle is a Dragon, he's gonna wanna loot all the corpses, I should probably prepare for that" is often useful. Or, "Stan is a Hound, he's totally going to want to find out what the barmaid knows about the missing caravan, I should probably give her stuff to say"
Best Answer
Do not cheapen relationships
Do not have a "romantic interest" NPCs, instead have real characters who may develop strong feelings for a PC.
Significant others are not quest items or things to be won through cheap tricks -- or for that matter expensive devices. To do so is to cheapen the life of the significant other. One cannot win the love of someone unless one lives in a romantic novel or uses chemicals whether potions or roofies. The latter kinda shifts the definition of "love".
You should aim to have NPCs that are fully fledged humans, with flaws and qualities, different physics and personalities. Let the role play between said characters bring them close to the PC. Make characters that the PCs want to spend time with, let feelings grow out of that.
If you wish to delve into homosexuality, you could have a same-sex NPC fall for one of the PCs and try to make their feeling known. This could be an interesting way to explore a different love story. Although, clearly an unconventional one. Ringil does spring to mind here.
Love as a "thing".
You can use love as a thing, this is not a bad thing in and off itself. For example:
Romeo and Juliet
Here love is taken as a plot point between two teenagers (the first one madly in love with someone else at the start of the play) who end up tearing their respective families out of their mutual hatred. Love here is but a McGuffin for the fulfilment of the story.
Les Liaisons Dangereuses
The Marquise de Merteuil and the Vicomte de Valmont are fine examples of what can be achieved in the art of seduction. If your characters are interested in that kind of romantic questing, then all the above is clearly less relevant. Targets are notches on the bed, nothing more than disposable pawns in the great game of seduction. In such a game, skill such as lying, subterfuge, and acting are paramount.
Tristan and Iseult
Here you have yet a different take on love. The whole quest is about the consequences of a falling in love: some tragic, some happy. This is the faery tale end of the spectrum: If your game is a faery tale where love is instantaneous and conquers all, then that's fine even if it is still a trope and thus needs to be done well.