Summary/synthesis of answers and discussion

This was fun, and I learned a lot.

Some Windows-specific cruft is inevitable if, on your POSIX system, you need to start your script with a #! line. If you have no alternative but to do this, then this line:

#!/bin/sh # 2>NUL

or possibly, if your OS is stricter, this line:

#!/usr/bin/env -S sh # 2>NUL

is probably the best it can get. It causes one blank line and one line of cruft to be output on the Windows console. However, you may be able to get away without a #! line: on most systems, one of the usual shell interpreters will end up executing the script (the problem is that it's not universally predictable which interpreter that will be - it depends on, but will not necessarily be identical to, the shell you use to invoke the command).

Beyond that tricky first line, there were some really ingenious cruftless solutions. The winning submission by jimmy23013 consisted of only two short infrastructure lines, and made use of the dual role of the : character to implement a "silent" line on both platforms (as a de-facto no-op in sh and friends, and as a label marker in cmd.exe):

:<<@exit/b

:: Arbitrary Windows code goes here

@exit/b
#
# Arbitrary POSIX code goes here 

It is possible to make such a script run on POSIX systems even despite CRLF line-endings, but to do this for most interpreters you have to end every line of your POSIX section (even blank lines) with a comment or comment character.

Finally, here are two variants on a solution I have developed based on everybody's input. They might be almost the best of all worlds, in that they minimize the damage from the lack of #! and make CRLF-compatibility even smoother. Two extra infrastructure lines are needed. Only one (standardized) line has to be interpreted by the unpredictable POSIX shell, and that line allows you to select the shell for the rest of the script (bash in the following example):

:<<@GOTO:Z

@echo Hello Windows!

@GOTO:Z
bash "$@"<<:Z
#
echo "Hello POSIX!" #
ps # let's throw this into the payload to keep track of which shell is being used
#
:Z

Part of the beauty of these heredoc solutions is that they are still CRLF-robust: as long as <<:Z comes at the end of the line, the heredoc processor will actually be looking for, and will find, the token :Z\r

As a final twist, you can get rid of those pesky end-of-line comments and still retain CRLF-robustness, by stripping the \r characters out before passing the lines to the shell. This places slightly more faith in the unpredictable shell (it would be nice to use { tr -d \\r|bash;} instead of (tr -d \\r|bash) but curly brackets are bash-only syntax):

:<<@GOTO:Z

@echo Hello Windows!

@GOTO:Z
(tr -d \\r|bash "$@")<<:Z

echo "Hello POSIX!"
ps

:Z

Of course, this approach sacrifices the ability to pipe stdin input into the script.

0 cruft lines, 0 cruft chars, 2 infra. lines, 21 infra. chars, CRLF ok

:<<@goto:eof
@echo Hello Windows!
@goto:eof
echo "Hello POSIX!" #

Removed the other solution.

17 characters using exit /b from Digital Trauma's answer:

:<<@exit/b
@echo Hello Windows!
@exit/b
echo "Hello POSIX!" #

I'll already post the solution I had been using, since it has already been beaten. It's courtesy of a colleague of mine who I think must have read the same blog entry as Digital Trauma.

#!/bin/sh # >NUL 2>&1
echo \
@goto c \
>/dev/null
echo "Hello Posix!"
exit
:c
@echo Hello Windows!

• Windows cruft: 5 lines (of which two are blank) / 30 chars
• OSX cruft: 0
• Infrastucture: 6 lines / 52 chars
• CRLF compatibility: only if the interpreter named on the #! line doesn't care (so for standard interpreters like sh and friends, it fails)

Score 0 cruft + 4 infra lines + 32 infra chars. LF & CRLF OK.

This is based off what I found at this blog, with the Amiga bits and other unnecessary lines taken out. I hid the DOS lines in commented quotes instead of using \ line continues, so that this can work with both CRLF and LF.

@REM ()(:) #
@REM "
@ECHO Hello Windows!
@EXIT /B
@REM "
echo Hello POSIX!

With either DOS CRLF or *nix LF line endings, it works on Ubuntu, OSX and wine:

ubuntu@ubuntu:~$ ./dosix.bat
Hello POSIX!
ubuntu@ubuntu:~$ wine cmd.exe
Wine CMD Version 5.1.2600 (1.6.2)

Z:\home\ubuntu>dosix.bat
Hello Windows!

Z:\home\ubuntu>exit
ubuntu@ubuntu:~$ 

To create this exactly (with CRLFs) on a *nix machine (including OSX), paste the following to a terminal:

[ $(uname) = Darwin ] && decode=-D || decode=-d
ubuntu@ubuntu:~$ base64 $decode > dosix.bat << EOF
QFJFTSAoKSg6KSAjDQpAUkVNICINCkBFQ0hPIEhlbGxvIFdpbmRvd3MhDQpARVhJVCAvQg0KQFJF
TSAiDQplY2hvIEhlbGxvIFBPU0lYIQ0K
EOF