What is the solution to the "surprise paradox"?

Well, I think it is just that you can't have a surprise party if you have been told there is going to be one. That makes it not a surprise anymore. This is different from his conclusion "it's impossible to have a surprise party on any day".

That's what I thought at first, but then we'd still be surprised when it happens. Is the fact that we get surprised when we logically know we shouldn't a true paradox, or just something funny about human nature?

The assumption that your friends are rational is flawed. On Wednesday, you don't know if they will surprise you on Thursday or ruin the surprise by planning for Friday.

I'm joining sides with engineer here.
Assuming that all your friends are as clever as you, you would have a contradiction of logic. However, I do not see an apparent paradox as it's possible to break the boundaries of the given scenario without breaking logic (as implied by engineer).

Therefore, if you knew there would be one it could still be on any given day.
Think about it this way:

It cannot be Thursday, but nor can it be Wednesday, or Tuesday, or for that matter Monday. You know this, and so do your friends (as we assume they are equally smart). This means, that you assume it does not happen at all, as there's a logical contradiction. Leaving you in the exact same position as where you first began - It's simply an infinite loop. You know there's going to be one, but no given point in time seems logical, and therefore you know not when.