tagged mails:

macro index S ":set confirmappend=no delete=yes\n<tag-prefix-cond><save-message>=archive\n<sync-mailbox>:set confirmappend=yes delete=ask-yes\n"

current only:

macro index A ":set confirmappend=no delete=yes\n<save-message>=archive\n<sync-mailbox>:set confirmappend=yes delete=ask-yes\n"

edit

macro index S ":set confirmappend=no delete=yes\n<tag-prefix><save-message>=archive\n<sync-mailbox>:set confirmappend=yes delete=ask-yes\n"

My fault, using tag-prefix instead of tag-prefix-cond, will apply the macro to tagged messages if present, else to the current selected.

For starters, you can use a macro like this to automatically jump to the new message:

macro index     .n      "<next-unread-mailbox><enter><next-new-then-unread><enter>" "Go to new mail"

Note however that if there are no new messages only Enter key will be pressed and the current message will be opened.

As an alternative if Maildir is used we could use a ~/bin/mutt-new.sh script that would check if there's new mail:

#!/usr/bin/env sh

if [ "$(find "$HOME"/.muttmail/box1/new -type f -printf '\n' | wc -l)" -eq 0 ]
then
    printf "I think there's no new mail\n" >&2
    printf "Press [ENTER] to continue\n" >&2
    read -r _
    exit 1
fi

echo 'push <next-unread-mailbox><enter><next-new-then-unread><enter>'

Add this to ~/.muttrc:

macro index     .n        "!~/bin/mutt-new.sh" "Go to new"

EDIT:

How about this: the following script will first check if there is new mail in the current mailbox:

#!/usr/bin/env sh

cur_mbox=${1/=/}

echo "$1" >> /tmp/PAR
echo "$cur_mbox" >> /tmp/PAR

if [ ! "$(find "$HOME"/.muttmail/"$cur_mbox"/new -type f -printf '\n' | wc -l)" -eq 0 ]
then
    printf "There is new mail in this mailbox\n" >&2
    printf "Press [ENTER] to continue\n" >&2
    read -r _
    echo 'push <next-new-then-unread><enter>'
elif [ ! "$(find "$HOME"/.muttmail/ -type d -name new -exec ls {} \; | wc -l)" -eq 0 ]
then
    printf "There is new mail in other mailboxes\n" >&2
    printf "Press [ENTER] to continue\n" >&2
    read -r _
    echo 'push <next-unread-mailbox><enter><next-new-then-unread><enter>'
else
    printf "I think there's no new mail\n" >&2
    printf "Press [ENTER] to continue\n" >&2
    read -r _
    exit 1
fi

Add this to ~/.muttrc:

folder-hook . 'set my_oldrecord=$record; set record=^; set my_folder=$record; set record=$my_oldrecord'
folder-hook . 'macro index .n "<enter-command>source \"~/bin/mutt-new.sh $my_folder |\"<return>" "Go to new"'

EDIT:

You said:

This is sub-optimal anyway, because if I have a new message, quit mutt, then open mutt again, this won't move me to the mailbox containing the "new" messages. (Presumably the mailbox is not unread any more.)

This can be fixed by:

set mark_old=no