Is there an elegant/easy way to set tab order on a VisualForce page?

You can set the tabIndex programmatically. While you do need to write a script, you can make it as simple or complicated as you'd like. Here's a quick example:

<apex:page doctype="html-5.0">
    <script>
    window.addEventListener('DOMContentLoaded',onload);
    function onload() {
        let tabIndex = 1;
        [...document.querySelectorAll('[data-order]')].forEach(section => {
            let items = [...section.querySelectorAll('input')];
            let dir = section.dataset.order == 'down';
            let len = items.length>>1;
            let reordered = [...items.filter((v,i)=>dir?!(i%2):i<len),...items.filter((v,i)=>dir?!!(i%2):i>=len)];
            reordered.forEach(item => { item.tabIndex = tabIndex++; });
        });
    }
    </script>
    <apex:form>
        <apex:pageBlock>
            <apex:pageBlockSection title="Section 1" html-data-order="down">
                <apex:input type="text" label="Field1" />
                <apex:input type="text" label="Field3" />
                <apex:input type="text" label="Field2" />
                <apex:input type="text" label="Field4" />
            </apex:pageBlockSection>
            <apex:pageBlockSection title="Section 2" html-data-order="across">
                <apex:input type="text" label="Field5" />
                <apex:input type="text" label="Field6" />
                <apex:input type="text" label="Field7" />
                <apex:input type="text" label="Field8" />
            </apex:pageBlockSection>
        </apex:pageBlock>
    </apex:form>
</apex:page>

This page only handles normal input fields (e.g. not select elements), and assumes two columns, and does not support reRender attributes, but this is not meant to be a perfect one-size-fits-all solution. The point is, you can do whatever you'd like to do, such as parse the table tr/td elements to figure out the order to use, etc. It's simply a matter of figuring out the JS you need.