I'd like to run an application (linux preferred, windows second
choice) other than MSN Messenger that will attach to MSN and check for
a buddy being online and not being away, and then invoke an action,
such as running a program.  Unfortunately, I've not been able to find
such a program.  So a great answer to this question would be "what you
need is xxx from xxx".  Thanks.

Trillian Pro (and maybe the the free version as well) has the ability
to execute programs and do other user defined actions on detection of
a user , trillian attaches to MSN AIM ICQ IRC and Yahoo

http://www.ceruleanstudios.com/

Ok, This is should be your answer.
If you prefer to do this with Linux, you actually need to use a
program called gaim. Gaim is a multiprotocol messenger client. The
Linux Version has far greater ability than the Windows Version of
Trillian or anything else Windows has to offer. Plus, you get the
source code. Keep in Mind you MUST download the latest version of
Gaim. This is because , Yahoo , MSN and such changed the security
settings and login parameters and the older versions just do not work.
You can get gaim for Linux here http://gaim.sourceforge.net/
Now, As for your question about running a program when someone logs
in. I have done this. With Gaim, you can use the buddy pounce feature
to execute a command when someone loggs in. Now, you may have to
actually run these commands as a shell script, that would be the easy
way to do it. If you do choose to run the command directly, I would
make sure to run it as command & , where commmand is what you want to
run , the & runs it as a background process. I had it setup so I got a
text message on my phone when someone logged in, that was before I
could use my phone to connect to yahoo. That way I got notifed if the
person was online and I could shoot them a mail message from my phone.

Hope that helps.