There are some steps before getting on embedded linux. As @KKToronto said, it would be nice if you have a desktop linux experience first. If you don't have any experience I recommend installing Ubuntu in your desktop/notebook in order to get some feeling with the OS.
To go from the desktop to the embedded world, at least on linux way, is relatively easy, if you're planing to develop FOR embedded linux. Almost all drivers interfaces, kernel calls, are the same. One program that runs on a desktop linux, can run on a embedded linux with minor alterations. The beagleboard platform is a good example, as @JobyTaffey noted. Some applications I developed can run on both desktop and the beagleboard without code alterations, just need to use the correct compiler.
Still on the "develop for embedded linux" topic: one of the main alterations is the compiler, mainly because almost all embedded processors that are powerful enough to run linux are ARM ones. From the C/C++/Java programmer it is almost like migrating from x86 to ia64.
If you want to get a deeper "embedded" experience as building device drivers for new hardware, accessing I/O ports on the board, control external equipments using linux, I'd go with Linux Embedded Primer. It is a great book to learn on low level stuff as how the device drivers are made, how to get access to fixed memory locations that represent some peripheral etc. (And it has an amazing lightsaber on the cover =) )
By going on the hardware side a deep microcontroller knowledge is really important, because you're going to be dealing directly with memory for peripheral configuration/access. Some operations may even require assembly knowledge, mainly interruptions or flash writing. It depends a lot on the microcontroller architecture.
If you have no experience on this, I'd recommend to start with arduino, as @stevegt noted, to get a hardware/electronics feeling and then proceed to a baremetal programming over any other processor, to learn some tricks related to hardware/software interface, that are somehow hidden on the arduino firmware or linux kernel.
As you can see that is much knowledge hidden on "embedded linux" expression. Keep in mind that you don't need to have all of it to build an embedded system. You need to focus on what side you want to learn first and get a pre-made system for the other: arduino for hardware first contact, beagleboard to learn programming for embedded linux, a baremetal processor for hardware/software interface.
Specifically for your case I'd recommend the beagle board. As you have some programming and microcontroller background, you can develop some applications in high level to get experience at linux programming and when you fell comfortable enough you could start hardware stuff with the available I/O's on the board.
Another answer: Stop using interrupts.
People jump to use interrupts too easily. Personally, I rarely use them because they actually waste a lot of time, as you are discovering.
It's often possible to write a main loop which polls everything so rapidly that's it's latency is within spec, and very little time is wasted.
loop
{
if (serial_bit_ready)
{
// shift serial bit into a byte
}
if (serial_byte_ready)
{
// decode serial data
}
if (enough_serial_bytes_available)
{
// more decoding
}
if (usb_queue_not_empty)
{
// handle USB data
}
}
There might be some things in the loop which happen far more often than others. Perhaps the incoming bits for example, in which case, add more of those tests, so that more of the processor is dedicated to that task.
loop
{
if (serial_bit_ready)
{
// shift serial bit into a byte
}
if (serial_byte_ready)
{
// decode serial data
}
if (serial_bit_ready)
{
// shift serial bit into a byte
}
if (enough_serial_bytes_available)
{
// more decoding
}
if (serial_bit_ready)
{
// shift serial bit into a byte
}
if (usb_queue_not_empty)
{
// handle USB data
}
}
There might be some events for which the latency of this approach is too high. For example, you might need a very accurately timed event. In which case, have that event on interrupt, and have everything else in the loop.
Best Answer
Check out the Digikey website http://search.digikey.com/scripts/DkSearch/dksus.dll?Cat=2556109
They have an online configurator where you can spec out your micro piece by piece... there are several that meet your spec. If you load the above page, be sure to scroll to the right, as there are tons and tons of options including package, memory peripherals etc...