Linux kernel is GPL-licenced. See GPL for that. GPL-licenced things can still be sold, but everybody has the right to redistribute it and is obliged to provide source for binaries if asked. So usually this leads to keeping everything free. Usually the kernel still needs to be customized for your application and if you don't do it yourself, then you have to order that from somebody.
Linux kernel mainline is free and you can get it from kernel.org. The latest 2.6.23 has most of drivers in it. Some patches that have not yet made in there are kept at
http://maxim.org.za/at91_26.html . Most of the interfaces are supported, including GPIOs, SPI, serial ports etc.
Your kernel size depends a lot on the feature set it has included. Usually it is around 1MB for AT91 devices with standard configurations. Add your filesystem and applications to it. Usually you want busybox in your filesystem, this is 1-2MB, too. So a VERY minimal system can fit into 4MB (we have done some ARM based systems with 4MB flashes). Depending the device you may wany 8MB, 16MB or even more on the device.
DHCP and Telnet daemons are userspace applications. Both should be included in busybox, if I remember correctly.