PostgreSQL How to optimize a query with ORDER BY and LIMIT 1?
A btree index on (sender,arrival) could help.  That would allow it to jump directly to the first-arrived message for a given sender.  

One on (arrival,sender) is less likely to help.  That allows you to jump to the first-sent message globally, but then you still have to walk along those messages until you hit one from the specified sender.  If that particular sender is new, or only sends messages to people who keep up on their inbox, then you might have to walk through most of the index  before you find a qualifying message.  It might help in that you only have to walk the index, not the index and table combined, but that would still be a much smaller win than the proper index of (sender,arrival).

Similarly, you would want another index on (box_id, arrival), not on (arrival, box_id).

Also, performance testing on a table with 800 rows is useless if the real table will have 100,000 rows.