There are several issues here in addition to the one you are thinking about.
There are two problems with an RC network: first, you need a small resistor to survive the variation in load current while running, which means you need a truly huge capacitor. Also, very slow rise in voltage may not reliably trigger power-on-reset behavior. So really you need your RC circuit, 555 timer or whatever to control a silicon power switch.
If you're going to use a silicon power switch, you might as well let the host Linux system control it with a GPIO that has to be explicitly enabled and driven by post-boot software. In fact this is practically critical, because you need to de-power that serial device any time the Linux system does a warm reboot and not just a power cycle, otherwise, that's going to fail, too. Imagine an unprecedented bug, a watchdog reset... and an eternal lockup - could anything be more opposite to the design intent of those mechanisms?
There are two common solutions for silicon power switching: one is to use a purpose made part, for example a USB downstream port switch chip, like the 5-pin version of the RT9742. These burn just enough in "off" mode to be questionable in a battery powered design, but otherwise give you a lot of application simplicity - there are others which are probably better. The other is to use a small logic-level PFET, but then you need an NFET to drive that with a 3v3 signal...
Once you're switching power to your device, great, right? Well, actually, No! It turns out that most devices prohibit having an I/O voltage outside the supply voltage, so if the chip is powered off, you have to make sure any UART line going to it is low, too. A few parts have exceptions to this rule in the data sheet, but unless you know you are facing one, you need to honor it - not doing so can cause damage, and it can also cause a failure to reset when "real" power is applied. There are various solutions, involving software pin settings, logic gates, or possible a MOSFET level shifter which can tolerate having its low voltage side (but not its high voltage one) unpowered. Of course maybe you never transmit to the device but only receive from it; if so the issue is more with pull-up resistors. And yes, even a pull-up resistor can inject enough current into a powered off device to cause startup problems.
the embedded Linux device aborts its boot sequence if it gets a serial message within the first second of power
Danger! Even if you fix what you think can cause this, what about what you haven't? That sounds like a common behavior of U-Boot, and the risk here is that if boot is permanently interrupted by a serial character, some sort of glitch could make your device fail to start. You probably want to think about making U-Boot command mode time out and eventually reboot - a bit of a writeup I did over on Stackoverflow after seeing an actual failure of this sort lead to spending an afternoon figuring out how to enable it.