Step 1: Linux Core
You don't need much for a router and usually Linux distributions come with a lot of packages you won't need to install. My idea and if I was more of programmer would be to strip out all of the extra components in the kernel that isn't needed for running, mounting, or configuring hardware. Would need to keep some packages over for the next step.
I would want to allow for the kernel and everything to be kept in the memory with no page file enabled.
Step 2: Install Programming Language Package
Could be Python, PHP, Ruby, Java, C, C++, or whatever your favorite is. You'll have to make sure you left enough of the kernel intact to install the package. I would probably use Python, and find a JIT compiler for it.
Step 3: Implement Router Specs
...And spend the next five years doing so.
Developing a router in Python, in my opinion, would be quicker to develop and debug the speculations of various router protocols than C or C++. I would much rather have the kernel and various packages in C and C++, but given the complex specs of the various protocols, I would rather implement them in another language.
How nice would it be to implement a firewall, packet filter, and intrusion detection system without using C! If implemented right, the backend could lend to three frontends: a cli for telnet, a gui for configuration using a monitor, and web based for HTTP configuration.
I would like for the first version to use more of the C or C++ packages with little to no modification to the kernel. Just a prototype to see how much would have to be installed to start building the Python Router.
The hard parts would be hooking the C/C++ APIs to allow for python to completely take over the rest of the packages. My guess would that PHP would really shine in this department, but Python also allows for hooks.
In about five years or so, a few of the protocols would be implemented and many of hours would have been wasted to no avail. Then the dist would die, and no one would care. It would of been fun though.
I'm looking to create a router or firewall and again, I'm looking towards Linux. I think Gentoo would be cool. I don't need anything too special and I believe I can still use the above to expand it to include some of the features that I'd miss in hardware routers. The Linksys RVS4000 would be good, but it doesn't work correctly. Something about the WAN port not seeing any cable modems, because of the signal not being boosted enough. Whatever. The only good thing on it is the Level 2 Managed Switch, so I'm thinking about building a gateway and then hooking into the router using a PC NIC.