How do I Moq a method that has an optional argument in its signature without explicitly specifying it or using an overload?

I believe your only choice right now is to explicitly include the bool parameter in the setup for Foo.

I don't think it defeats the purpose of specifying a default value. The default value is a convenience for calling code, but I think that you should be explicit in your tests. Say you could leave out specifying the bool parameter. What happens if, in future, someone changes the default value of b to true? This will lead to failing tests (and rightfully so), but they will be more difficult to fix because of the hidden assumption that b is false. Explicitly specifying the bool parameter has another benefit: it improves the readability of your tests. Someone going through them will quickly know that there's one Foo function that accepts two parameters. That's my 2 cents, at least :)

As for specifying it every time you mock it, don't duplicate code: create and/or initialise the mock in a function, so that you only have a single point of change. If you really want to, you can overcome Moq's apparent short-coming here by duplicating Foo's parameters into this initialisation function:

public void InitFooFuncOnFooMock(Mock<IFoo> fooMock, string a, bool b = false)
{
    if(!b)
    {
        fooMock.Setup(mock => mock.Foo(a, b)).Returns(false);
    }
    else
    {
        ...
    }
}

Just encountered this issue today, Moq doesn't support this use case. So, seems that overriding the method would be sufficient for this case.

public interface IFoo
{
    bool Foo(string a);

    bool Foo(string a, bool b);
}

Now both methods are available and this example would work:

var mock = new Mock<IFoo>();
mock.Setup(mock => mock.Foo(It.IsAny<string>())).Returns(false);

Using Moq version 4.10.1 I have been able to do the following

With Interface:

public interface IFoo
{
    bool Foo(string a, bool b = false);
}

And Mock

var mock = new Mock<IFoo>();
mock.Setup(mock => mock.Foo(It.IsAny<string>(), It.IsAny<bool>())).Returns(false);

Resolves a call to Foo with the first parameter okay