Honestly- The best thing that you can do is to figure out how they're going to get along with you, and how well they can find solutions to problems.
They say that the first few employees really determine the culture of a startup, and you want people who can adjust to whatever job is necessary, and solve problems quickly and move on to the next thing in the ever-growing list.
I read an article online (Was it Joel? Seth? Not sure), who argued that there are really two types of programmers- Problem Solvers, and Cogs.
Cogs are the people who can tell you every line of code in a TCP/IP stack, or squeeze amazing performance by reprogramming your server-code in assembler. They're the people you bring in to solve problem foo-
"We need a guy who kicks butt in SQL to optimize this thing" Let's find one."
That's great, and that's amazingly useful.. But not for the first few people for a startup.. For a startup, I'd worry more about coming up with solutions to problems that we have. Someone who can pick up Lisp or Ruby or (insert language of the week) in a few days more useful in those crucial early weeks than someone who can eek every bit of performance.
Focus on the hard stuff first, like building something people actually want to use. THEN, hire people to help specific elements.
With any luck, by that point you'll have created a corporate culture that encourages flexibility, and they'll come around ;)
-Colin
In practice, I try and hire people that have blogs wherein they showed knowledge as well as serious and deep thinking about the type of problems I want to hire them to solve.
The only person I've ever truly thought did an excellent job I hired this way. I didn't know him. I didn't look at a resume. I had one conversation with him. I just read his blog, and I could tell from his writing that he would do a good job. Actually, his blog was just his fiction writing and he was a UI designer and coder but I could still tell from his thinking. He was so smart--a structured, logical, deep and creative thinker. It was clear to me that he would do a good job. He did. I tend to be a perfectionist, and he was the only person I've ever hired that did a perfect job. I had absolutely no criticisms about him. He always exceeded my expectations. It was amazing. I love working with the best people--nothing is more fun.
If they didn't have a blog, I'd tell them to write down their thoughts every day for a few weeks and then I'd read it. I believe that you can't tell anything about anyone except how they behave over time. People lie and misrepresent themselves. But it's pretty much impossible to misrepresent yourself over a period of time.
I might try and give them a few of my problems to work on as well. But, if someone isn't the quickest thinker and can't answer a problem I give them in an hour-long interview I really don't care. What if they're amazing problem solvers but they just take overnight? One of the smartest people I know is like this.
With a blog, or writing over time, you also get a sense of how well they can articulate their ideas--if they have amazing ideas but they can't articulate them well, then the quality of their ideas doesn't matter. If for some reason they're terrible writers but still smart, you can just have them create a podcast. If they can't do either, then they can't articulate themselves enough to be useful to a company.
Watching their thinking over time, you can see how many ideas they generate, since you don't just want people that will only solve the problems you have. You want people that see things you can't and generate ideas themselves.
I don't care about how well people fit in. A start-up isn't a clique of best friends, although you certainly need people that you can be bluntly honest with and can be bluntly honest with you. It's better if you like them, of course, but I'm never trying to build any kind of culture except a culture of excellence--well, excellence on deadline.
Another thing I've always wanted to try is just to hire someone for two weeks and give them non-critical tasks to do. I could see if they met deadlines and how they actually worked. The best way of finding out if someone can do something is to watch her do it.
I'd also argue that how people fit in is important. If you don't care about fit when you hire, you end up with a company of individuals instead of a team.
I do agree that the best interview is one where the candidate actually does the type of work that is to be expected of him/her.
For co-founders, you shouldn't even have to interview. Find the best people that you have worked with before in school, or on the job. You can then be assured of their creative and intellectual abilities, as well understanding how you'll work together as a team.
For other positions, you're obviously going to want to look for smart people, but a key thing for a small startup is to look for smart people who can do many different things well. For example, I'd be more inclined to choose a s/w eng who has done well designing a web app, and has designed embedded software for a consumer electronics device than an eng who has worked only on web apps for their entire career.
As for the second part of your question, I'd agree with e1ven - neither type of question is key, although they do help establish technical ability & creativity.
But my experience diverges from e1vens' in at least one respect - you don't need to choose between problem solvers and cogs (at least as he has defined them). I have worked with people who can give you tons of detail on specific technical areas, but can also come up with great solutions outside of their technical domains or pick up language X really quickly. It's rare, but people that have both qualities certainly exist.