With public-key algorithms, you don't do encryption and signing of the message using the public-key algorithms themselves. Instead, you use traditional symmetric algorithms for encryption and hash algorithms for signing, then apply the public-key algorithms to those results.
What you're asking for here can actually be thought of as two entirely-different processes. The first is to encrypt the message to the public key of the recipient. The second is to sign the encrypted message with your private key.
As you noted, RSA can only handle encrypting and signing message sizes up to the sizes of the modulus. However, it's actually worse than that: using RSA on messages larger than a certain percentage of the modulus size is actually also insecure. Proper use of RSA requires dedicating a certain portion of the input space - actually, most of it - to data called "padding". You fill in the low part with the encryption key or hash you're encrypting or signing, then fill the upper part with padding according to the specification you are using. The recipient then validates that the formatting and padding is as expected on the other end. You must do this, or your encryption system will be broken by attackers if they want.
A proper implementation is going to require secure random number generation. Generating the public and private keys has to be done using secure random number generation, but encryption is going to require this as well. Don't try to implement secure random number generation yourself; let your operating system do that for you. In Windows, use
CryptGenRandom; on UNIX systems such as Linux and Mac OS X, open the fake file
/dev/urandom and read bytes from it.
To encrypt a message with RSA, select a symmetric encryption algorithm. I recommend 128-bit AES (Advanced Encryption Standard) in CBC (Cipher-Block Chaining) mode, a very typical setting. For each message you encrypt, generate a 128-bit (or 16-byte) random encryption key and a 16-byte IV (Initialization Vector). The key and IV are for this message specifically, and shall never be used again.
Combined with the key and IV, encrypt the message using AES. AES is a block cipher with a block size of 16 bytes; this means that it can only encrypt messages whose size is a multiple of 16 bytes. To handle messages that are not a multiple of 16 bytes, a technique called Ciphertext Stealing can be used. Because we're going to send the IV inside the RSA-encrypted area, you're allowed to change the IV as part of the ciphertext stealing technique if the whole message is smaller than 16 bytes.
With the message encrypted, we now do the RSA encryption step. With RSA, we can only encrypt a small message, but what will it be? In this design, our message is 32 bytes: the key, and the IV. This means that you need a key size of at least 1024 bits (128 bytes). Let $C = AESCBC(IV, M)$ be the symmetrically-encrypted message.
Look up RFC 2437 and find "RSAES-OAEP". "Optimal Asymmetric Encryption Padding" is a good choice of how to fill out the number $m$ given the message $K$ $||$ $IV$; that is, $K$ and $IV$ concatenated. Once that's done, you calculate $c = m^d$ mod $n$ for RSA as you've known. The total encrypted message is $c$ || $C$.
Next, we sign the combined message $V = c$ $||$ $C$ using the sender's private key. Since $V$ is probably too long, given that $C$ is the same length as the unencrypted message, instead of signing $V$ directly, we sign the hash of $V$. Choose a good hash algorithm; SHA-256 is a good choice.
Once again, consult RFC 2437, this time the RSASSA-PSS section. This section describes a method to generate a signature from a private key and a "message", which in our case will be $M = SHA256(V)$. This generates the final signature, $S$.
Send $S$, $c$ and $C$ to the recipient.
The inverse on the recipient's side should be straightforward to understand if you've implemented the above. First, the recipient calculates $SHA256(c$ $||$ $C)$, which is equivalent to $SHA256(V)$ and $H$. Next, the recipient applies RSASSA-PSS-VERIFY to check the signature. As on the sender's side, $H$ is the message $M$ when it comes to RSASSA-PSS. If RSASSA-PSS succeeds, $S$ is an authentic signature of $c$ and $C$.
Now the recipient does an RSA decryption of $c$ to recover $m$ using RSAES-OAEP-DECRYPT. The low 32 bytes are $K$ and $IV$. Use key $K$ and initialization vector $IV$ to AES-CBC decrypt $C$ back into the original text; don't forget about ciphertext stealing if you used it. (You can tell whether the sender used it by whether the number of bytes in $C$ is a multiple of 16.)
If an error is detected at any time, abort. Don't tell the other side any specifics of why.
I would have given more links if my reputation were high enough to allow it.