my smc and d-link routers have worked fine.. can you change the config and open the ports up? here's a small list (service,port):
AIM, 5190
iChat AV (Audio?), 5060
iChat AV (Video), 16384-16403
iChat (Rendezvous), 5298
also make sure that these ports are open on your mac (you can specify in the Firewall tab of the Sharing system preference pane).
it's probably possible to buy routers w/out these firewalls, but it should be possible to adjust them or even disable them when they're built-in.
another option is to get a mac-compatible pci network card and share the connection from the internet through your built-in ethernet to the other computer through that card. a disadvantage here is that the first computer has to be on and running internet sharing whenever the second computer wants access. also, the first computer has to be a powermac (because it needs a free pci slot) and it might be hard/expensive to find a mac-compatible network card.