The first thing you have to remember is that you're never going to make an extremely sweet liqueur with a delicate flavor, like an amaretto or melon liqueur, into something it's not. You can complement or supplement, but you'll never mix a Midori drink that loses the sugar while keeping the melon flavor in the forefront; you'll either have to live with the sweet note or you'll cover the melon if not blow it away completely.
The recipe I always use when experimenting with cocktails is "two parts strong, one part sweet, one part sour". You pick a mother liquor (your 80- to 150-proof "base"), add a sweet note, usually a sweet liqueur like a curacao or amaretto, or a syrup like grenadine, then balance it with a sour note like citrus juice, pomegranate juice, or sour liqueurs like limoncello, sour apple, sour cherry, etc). This usually, if you choose em right, gives you something close to the flavor palate you were after when you chose the three parts; then you can tweak the proportions to balance the individual ingrediants' strengths and weaknesses.
For instance, tequila, triple sec and lime juice in these proportions makes a decent "up" margarita, but many will find it too strong and a bit sour; the traditional mix is 7-4-3, which compared to the 8-4-4 (2-1-1) experimental mix brings out the sweet but also-citrusy triple sec a bit more.
Back to the case in point; Midori is your "sweet", and it definitely is so. It's also on the fruity side, so you can either complement it with herbs or cream, or supplement it with more fruit, but don't try to make Midori something it isn't with something like smoke or earth (translated; stay away from whisky unless you're willing to drink your mistakes). Lemon/lime juice is usually a winner as a strong fruity sour note. Pomegranate juice is less powerfully acid, but also less citrusy, so if you don't want it to taste like a lemon lollipop you can give it a try. The problem is that mixing red and green gives you brown, so it won't be particularly attractive. I've used vinegar-based liquids as a sour before (try vodka, vermouth and pickle juice sometime) but it's not the right note for Midori. Chambord (black raspberry; generally more tart than sweet) could be promising; never tried it. Chambord is 33 proof and Midori is 46; those are different enough in specific gravity (as a rule, higher proofs are lighter and sugar is heavier) that if you're careful, you can layer them Midori over Chambord, which makes a Christmas Shot (red and green).
Bitter can also counter sweet, but you have to be REAL careful; forget the 2-1-1 mix and just put your strong and sweet together, then add a dash of bitter at a time until it balances. Campari is an option (the "Sloppy P***y", if you dare to Google that term, has Midori battling Campari and gin among other things), but I've never cared for it as a mixer and don't keep it in my personal cabinet. Anise-flavored drinks, such as Galliano, ouzo or absynthe, have a bitter note as well as some colors and other properties that could make an interesting looking drink. Most people forget that chocolate is actually a bitter flavor, and it's only candy because chocolatiers slurry up the cocoa in a heap of sugar, cream and butter. You can try a dark chocolate liqueur like Mozart, Sabra or Godiva Dark, mixed with Midori and/or a base like white rum or vodka (again, try layering them when you see a difference more than about 10 proof; you're playing with a nice vivid green here, so let it show).
There's nothing wrong with keeping it on the sweet side, either. Cream can complement sweet nicely without adding more sweet or trying to take it away. Bailey's does add more sugar, so be careful with that one. Milk/cream, vanilla ice cream etc are all good avenues to add a cream note while keeping Midori's melon flavor and not making it sickeningly sugary. The Green Russian is a take on the White Russian (vodka, Kahlua, milk) substituting Midori for Kahlua. Bols Parfait d'Amour (they start with blue curacao and add vanilla, almond and rosehips which make it purple) is 54 proof, so it'll layer on top of Midori, making a Mardi Gras.
Sodas will add a little acid, a little bitter and a little sweet, and are good to water down the syrupy consistency of Midori. Midori and ginger ale and an M7 (Midori and 7-Up) are obvious choices; I'd stay away from cola as you'll descent back into syrupy sweet land again. Try adding Midori to a vodka spritzer (club soda or tonic water) to sweeten it a bit.
Stay away from other syrupy-sweet ingredients. Grenadine is a no-no unless you're layering a shot and need a heavy red. Midori and amaretto generally have the same place in the profile, so one is typically used instead of the other to change up a drink.
Despite anything I say to do or not do, you'll find an example of something that works if you look hard enough. For instance, there is a Scotch and Midori drink called a Wicked Sky, and a generic whiskey/Midory cocktail called a Midtown Muse, both of which mix pit whisky against Midori which I recommended against. The Quick F**k is a layered shot of Baileys, Kahlua and Midori, mixing the sweet fruit of Midori with extra sweet and cream in the Bailey's against earthy Kahlua coffee tones.