Thanks for the great advice. I have just been struggling to decide between different projects. Do you think a consumer mobile app would have enough degree of difficulty to impress companies?
Even if the app is simple and has a grand total of 2 users, it should provide decent conversation fodder and peg you as disciplined, detail-oriented and big-picture-focused. For example, if you have not built something obvious in (internationalization, in-app purchases, deep links), throw in an explanation of how you're aware of it and made sure it fits into the next release.
One quote from Sam Altman' startup class that stuck with me was (I believe it was from Brian Chesky) someone asking two builders what they were working on laying bricks. One said "I'm building this wall", another said "I'm building the cathedral". Be the second guy.
If I had to hire for a product manager, an indication of the skills associated with this would be what I would look for. Critical thinking and diplomacy are crucial skills, in addition to all the things you have mentioned.