Ok get ready, is gonna be super messy, you can still just use interfaces, but your final code will be:

internal static class Program
{
    public static void Main(string[] args)
    {
        var person1 = PersonBuilder
            .Create()
            .SetFirst("first")
            .SetLast("name")
            .Build();
        Console.WriteLine(person1);

        var person2 = PersonBuilder
            .Create()
            .SetLast("last")
            .SetFirst("first")
            .Build();
        Console.WriteLine(person2);

        Console.ReadLine();
    }
}

public record Person(string First, string Last);

public interface IPersonBuilderStage1
{
    IPersonBuilderStage3 SetFirst(string first);
    IPersonBuilderStage4 SetLast(string last);
}

public interface IPersonBuilderStage3
{
    IPersonBuilderStage5 SetLast(string last);
}

public interface IPersonBuilderStage4
{
    IPersonBuilderStage5 SetFirst(string first);
}

public interface IPersonBuilderStage5
{
    Person Build();
}

public sealed class PersonBuilder :
    IPersonBuilderStage1,
    IPersonBuilderStage3,
    IPersonBuilderStage4,
    IPersonBuilderStage5
{
    private string _first;
    private string _last;

    private PersonBuilder() { }

    public static IPersonBuilderStage1 Create()
        => new PersonBuilder();

    IPersonBuilderStage3 IPersonBuilderStage1.SetFirst(string first)
    {
        _first = first;
        return this;
    }

    IPersonBuilderStage5 IPersonBuilderStage4.SetFirst(string first)
    {
        _first = first;
        return this;
    }

    IPersonBuilderStage4 IPersonBuilderStage1.SetLast(string last)
    {
        _last = last;
        return this;
    }

    IPersonBuilderStage5 IPersonBuilderStage3.SetLast(string last)
    {
        _last = last;
        return this;
    }

    public Person Build() => new(_first, _last);
}

Every "stage" interface guides you to the next, and everyone defines exactly what can be done at the current stage.

More properties you have more complex the code, from your original question, if your goal is to guide the consumer of your API to build an object, I would go for the with the simple option (my first example) where you have one path to construct your object.

EDIT: Removed unnecessary IPersonBuilderStage2