well, yahoo (if im right) wont allow 3rd party clients (i think the gaim guys are lookin to fix it ?), but they do have clients for linux on messenger.yahoo.com (im using the debian one - no issues).
for msn, i use amsn - it exactly the same as msn, and in cases better (but no cam support).
theres even linux aim.