OP I say figure out what role you want to play in doubles first, then pick a character that suits that role. Partner with someone who compliments that role / patches up weaknesses.
EX: I like playing support in doubles. I'd rather back up my partner and capitalize off of their openings than rush in and create them myself. Captain Falcon suits my style because he has the mobility to be wherever he needs to be and raw power to make capitalization hurt (Knee, Dair, Fsmash, Fair).
Since I'd rather sit back, I'm better off teaming with a character and partner who wants to be the aggressor. So I'd like MK, Sheik, Diddy, Sonic (not as safe, but good pressure), Mario, etc. to be my partner to start things up.