Ok. What are you passionate about? What is your background now?
First step now, is to figure our what each of your strengths is/are, and then create a list of potential ideas that spark each of you, then choose the one that (a) ignites you both, (b) has a realistic revenue model, and (c) can be built without the need for investor capital.
Make sure you choose something that actually has customers you can get to, not something that has revenue potential when you say "If we can just get 1% of the population..."
Lastly, enjoy the journey.
We did this list mentality to start, but after awhile had crossed off the ideas in each industry we both were excited about.
For example, Uber appears to be the end of the taxi business, but it opens up a whole market to developers. You have a beautiful imbalance now, all those taxi drivers and cab companies are heavily incentivized to compete with Uber or lose their companies/jobs.
If there was (and there might be, idk) a platform that allowed all the cab companies to aggregate into an uber-Uber, there's a market for that with known customers. The only obvious issue I see is that in order to make this work, the cab companies would have to give up their fights to block Uber using municipal codes as they are now.
Anywhere you have an imbalance, there's a potential market. The problem is, if you're not on the demand side, your product has the potential of a short lifespan unless it corrects the imbalance.
Google did this with ads, Uber with rides, AirBnB with rooms, tinder with.. well, you know.
Each of these markets had an unseen demand side which each of the companies exploited. Find an unfilled demand and fill it. It doesn't need to be huge, but if it's in the way of someone already moving there, you greatly increase your chances of being acquired.
The idea should not be a spur of the moment thing. It has be well researched, pros and cons analyzed etc. I am curious if the creator of the thread can elaborate on why the need for a startup. I am even more surprised he was able to find a co-founder without an idea.