That being said, just because you can brainstorm with someone doesn't mean you'll be successful. You could be mediocre which is why it's easy for you to find someone you can brainstorm with. But it is a sign of a good cofounder.
Mediocre non-brilliance is better if they can drop those walls, and admit where they need help, because hard work and drive gets things done.
In larger companies you have to work with people you respect but don't like. Don't do that in a startup, it takes away the passion and the motivation.
I would suggest not trying to "find" a cofounder -- the "cofounder" idea of a word is itself a weirdness here, almost mythologized -- you're either there at the beginning or you are not, and if you are, you're a founder. If that person's name wasn't just JUMPING at you when you had a company idea, you don't want one, or need one.
If you did not naturally find an idea with someone, do it yourself. Be the CEO and hire the help you need (and get rid of them if they don't work out), but don't give up control.
This is basically marriage (you'll probably spend more time with them than family at times) -- and you don't marry someone you don't love. You must really really know them. And that takes years, and can end your startup if you choose incorrectly.
If you are trying to get someone to implement your business idea, hire technical help. If you are technical and need business help, hire somebody to be your VP of Sales/Finance/whatever.
No. We were all thinking that.
Edit: You didn't see 2 total strangers with no history and completely different ideologies having problems running a business together? That is what these downvotes and OP seem to suggest.
We failed probably because of not what you're thinking. My business co-founder brought more to the table than I could imagine. I've gained a lot of respect for the hard work of sales, marketing, fundraising, and the people that make these tasks seem so easy.
We got hundreds of customers, made $10k revenue per month, and had a staff of 5 at one time. All bootstrapped over the course of 12 months.
The thing is, we were not happy working with each other. When shit hits the fan (which happens often in a new business), we just get on each other's nerves. On paper, we have perfectly complimentary skill set. He's a charming people person. I'm a proficient developer. In reality, the fact that we're so opposite means that we're always seeing and doings things differently. When we're in a grind, he wants to hi-fives to boost morale and I want to put my head down to ship faster.
If I were to do it again. I'd find a smart, hardworking person that brings me energy and that I'd bring them energy when the shit hits the fan. I wouldn't care if they're a CEO, CTO, C-whatever-O. I'd look for someone that I'd enjoy working with above all else.