I assume the cause of this is the high latency in your cell phone's data connection. I can eliminate most of the latency of using ConnectBot on my Android phone just by being connected to Wifi instead of HSPA.
readline should really emit some character when it enters and leaves line-editing mode, so the line-editing can happen on the client side. It's not annoying to wait 200ms after you've finished your command and are waiting for the output. It is annoying to wait 200ms for your backspace to take effect.