Earlier this year I installed Linux on my $40 Motorola router. Since then, I've discovered various ways in which this can be beneficial and turn my $40 router into something closer to a $400 Cisco router.
On the performance side, I overclocked the CPU from the stock 200MHz to 216MHz, which gave me a noticeable increase in routing bandwidth: almost 6Mbps, for a total of 18Mbps. If I install a suitable heatsink, I can take the BCM4712 CPU all the way up to 300MHz. Using DNSMasq for DNS forwarding eliminated many of the problems that stemmed from Motorola's firmware, and with iptables I can use DHCP with my laptop and still maintain my port forwards, which saves me quite a bit of time and effort.
In terms of security, I'm no longer vulnerable to a remote privilege escalation bug that Motorola decided not to fix in their own functional firmware (though an updated, considerably more Spartan build did fix this issue). The Linux driver for the wireless chipset supports WPA2 with the CCMP protocol and AES encryption, as well as a mixed mode that allows for backwards-compatibility with WPA/TKIP-based devices. I can also create a virtual interface, ensure that it's not bridged with the rest of the network, bandwidth-throttle it using tc, and set it up individually with 128-bit WEP encryption, which minimizes the severity of an attack on the WEP-enabled channel.
I've found that the router is very useful for running certain services that I don't necessarily want to dedicate a separate machine to. For example, it runs a Kai daemon so that I can get my Xbox online, and automatically updates my DynDNS hostname when my IP address changes. I have ttraff monitoring my monthly bandwidth usage and writing it back to NVRAM so that I can go see how much I upload and download in a month. QoS services ensure that BitTorrent doesn't hose my networking capacity anymore, while I also set up a PPTP VPN server with 128-bit RC4 encryption and LZW compression so that I can (semi-)securely access the network while away from home. If I ever run out of space for applications, I can always mount a SMB share elsewhere on my network using Samba and run them from there instead of the RAM disk.
I should of course mention that all of this is completely free. If your router is built on the Linksys WRT framework (like mine) or runs on a standard x86 PC, DD-WRT can get it to do some rather interesting things that you may find both interesting and useful.