I ended up creating a couple of custom macros to achieve this.
So in my MediaGallerySelectedItem transformation I have:

<a href="<%# MediaLibraryFunctions.GetMediaFileNext(UrlHelper.CurrentURL, Eval("FileID")) %>" class="next">Next</a>

<a href="<%# MediaLibraryFunctions.GetMediaFilePrevious(UrlHelper.CurrentURL, Eval("FileID")) %>" class="next">Previous</a>

These functions are then defined in App_Code > CMSModules > Media Library > MediaLibraryFunctions.cs

    public static string GetMediaFileNext(string currentUrl, object fileId)
    {
        string albumUrl = UrlHelper.RemoveParameterFromUrl(currentUrl, "fileid");

        return MediaLibrary.GetNextUrl(albumUrl, Convert.ToInt32(fileId));        
    }

MediaLibrary namespace is in a class library I built outside of the Kentico sln.

Here is the code for that class, you need to make sure to reference the dll and include the using statement for it. Alternatively you should be able to put this right in the App_Code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NatureValley.Common
{
    public static class MediaLibrary
    {
        /// <summary>
        /// Gets the url to the next File in that album
        /// </summary>
        /// <param name="albumUrl"></param>
        /// <param name="fileId"></param>
        /// <returns></returns>
        public static string GetNextUrl(string albumUrl, int fileId)
        {
            string nextUrl = albumUrl + "&fileid=";
            int[] mediaFiles;
            using (NVdatabaseDataContext db = new NVdatabaseDataContext(Globals.ConnStr))
            {
                var mediaFile = db.Media_Files.Single(mf => mf.FileID == fileId);
                string filePath = mediaFile.FilePath.Substring(0, mediaFile.FilePath.Length - mediaFile.FileName.Length+1);

                mediaFiles = (from mf in db.Media_Files
                                 where mf.FilePath.StartsWith(filePath)
                                 orderby mf.FileID
                                 select mf.FileID).ToArray();
            }

            if (mediaFiles != null && mediaFiles.Length > 1)
            {
                for (int i = 0; i < mediaFiles.Length; i++)
                {
                    if (mediaFiles == fileId)
                    {
                        if (i != mediaFiles.Length - 1)
                        {
                            nextUrl = nextUrl + mediaFiles[i + 1].ToString();
                        }
                        else
                        {
                            nextUrl = nextUrl + mediaFiles[0].ToString();
                        }
                    }
                }
            }
            else
            {
                nextUrl = nextUrl + fileId.ToString();
            }
            
            return nextUrl;
        }

        /// <summary>
        /// Gets the url to the previous File in that album
        /// </summary>
        /// <param name="albumUrl"></param>
        /// <param name="fileId"></param>
        /// <returns></returns>
        public static string GetPreviousUrl(string albumUrl, int fileId)
        {
            string nextUrl = albumUrl + "&fileid=";
            int[] mediaFiles;
            using (NVdatabaseDataContext db = new NVdatabaseDataContext(Globals.ConnStr))
            {
                var mediaFile = db.Media_Files.Single(mf => mf.FileID == fileId);
                string filePath = mediaFile.FilePath.Substring(0,mediaFile.FilePath.Length - mediaFile.FileName.Length+1);

                mediaFiles = (from mf in db.Media_Files
                              where mf.FilePath.StartsWith(filePath)
                              orderby mf.FileID
                              select mf.FileID).ToArray();
            }

            if (mediaFiles != null && mediaFiles.Length > 1)
            {
                for (int i = 0; i < mediaFiles.Length; i++)
                {
                    if (mediaFiles == fileId)
                    {
                        if (i != 0)
                        {
                            nextUrl = nextUrl + mediaFiles[i - 1].ToString();
                        }
                        else
                        {
                            nextUrl = nextUrl + mediaFiles[mediaFiles.Length - 1].ToString();
                        }
                    }
                }
            }
            else
            {
                nextUrl = nextUrl + fileId.ToString();
            }
            
            return nextUrl;
        }
    }
}

Notice I am using linq to sql here so you'll have to set that dbml up too. I pointed to the table Media_File in the database.

This ended up working well, but seemed to be a lot to get what I needed. Is there a simpler solution out there?