Encrypting messages to be sent over a socket I recognize the importance of properly implement cryptographic functions. Since this is my first time using them I really wanted a second opinion on my method. Therefore, I was wondering if my method of sign-then-encrypt as implemented would be a valid method of safely achieving those results.

def gen_keys(size):
    print('Generating new keys...')
    pubkey, privkey = rsa.newkeys(size, poolsize=8)
    print('Keys generated!')
    return pubkey, privkey


def encrypt_full_message(message, pubkey, privkey):
    parts = textwrap.wrap(message, 245)
    message_to_send = b''
    for part in parts:
        part = part.encode('utf-8')
        signature = rsa.sign(part, privkey, 'SHA-256')
        encrypted_message = rsa.encrypt(part, pubkey)
        message_to_send += encrypted_message
        message_to_send += signature
    return message_to_send

def decrypt_full_message(message, privkey, pubkey):
    parts = [message[i:i+256] for i in range(0, len(message), 256)]
    messages = parts[0::2]
    signatures = parts[1::2]
    fmessage = b''
    for signature, message in zip(signatures, messages):
        message = rsa.decrypt(message, privkey)
        if rsa.verify(message, signature, pubkey):
            fmessage += message
        else:
            print('Message has been tampered with.')
    return fmessage
gen_keys()

It's generally a bad idea to have both calculation logic and output in the same function. What if you have to move your system to somewhere you can't use print() such as a batch process or web server? Use the logging module instead, that way it can easily be redirected.
encrypt_full_message()

The problem with this one is that you are constructing many temporary string objects. Python strings don't support the append operation natively; what you're doing is throwing away the old string and constructing a new one. A better way would be to write an encrypt_and_sign_single_part() function and then this whole function would just be

def encrypt_full_message(message, _pubkey, privkey):
    return ''.join([encrypt_and_sign_single_part(part,_pubkey,privkey) for part in textwrap.wrap(message, max)])


Also why did you put the underscore before pubkey? That doesn't match the naming conventions you're using.

Similar warning about using print(). Really, check out the logging module.
decrypt_full_message()

AAAAAAAAGH! Did you even test this with a multi-part message? You're going to get n^2-n warnings for every n part-pairs!

The biggest problem is you separate the parts in two and then use the two streams separately. Python has tuples, use them. That way you only can use one loop, rather than the incorrect nested loops you have now.