Analyze the firmware. If it doesn't pass a checksum, it could be compromised. If the software doesn't pass a checksum, it's compromised. Strange traffic coming out of the router is a bad sign. If the router is running analysis on your packet, you will likely experience diminished throughput on the high end because of limited resources on the router.

I think if you can go without enabling remote access to a router, then you should. This will protect the router itself from direct login attacks from the outside, but if somebody compromises a machine on your LAN, you're boned. If you can't, and you have security concerns, you need to establish metrics of verifying whether or not the router is behaving the same way it was when it came out of the box and (presumably) was not compromised. Like I mentioned, software/firmware checksums are a possibility (these could be hard, though...getting a router to dump its internals out probably isn't a feasible solution for everything), but YMMV depending on what you do and what you need your router to do. My biggest guess at the tell-tale sign of a compromised router is that it just starts slowing down.