How do I change the size limits of messages in a mailbox?
You can't really set a limit on the individual messages already in a mailbox, but you can place limits on the message sizes that will pass through the various connectors. And you certainly can place limits on the total mailbox size.
In the properties for the Message Transfer Agent (MTA) you can specify a maximum message size, but I generally don't recommend it. You don't mention what your goal is here—keeping mailbox size down or preventing slow connectors from getting clogged—so it's hard for me to make a specific recommendation.
Let me leave it at this: each of the connectors (IMS, X.400, etc.) have in their properties dialogs fields where you can specify a maximum message size they'll pass. Be careful when setting these, though, it would be a shame to reject important and legitimate business mail simply because it exceeds some arbitrary size limit. Try to set limits only on the connectors that really need to be constricted for performance or reliability reasons.
If your goal is keeping mailbox size low, try encouraging your users to use AutoArchive and to keep their mailboxes fairly clean. If that doesn't work, setting mailbox size limits can help to encourage them to clean up after themselves. You can find those settings in the individual mailbox properties pages.
To set a default limit for all mailboxes go to the properties of the Private Information Store object on your server. The storage limits can be set on the General tab.
(Note: I assume you left all of your mailboxes set to "use Information Store Defaults" as the limit settings.)