I'm building an All-City Space Horse with 700C Velocity Dyad rims and 45mm Velo Orange fenders. What do you think the maximum tire width will be that I can use? I'm thinking of getting Schwalbe Little Big Bens, but I'm not sure if that will fit.
tl;dr: The 38-40mm Little Big Ben tires will fit your bicycle but (maybe) not your fenders
The webpage for http://allcitycycles.com/bikes/space_horse clearly indicates that your thickest tire is a 700c x 42.
Since the Little Big Bens are 38-40mm in width, you should be ok with them on the Space Horse ... except ....
.... the only Velo-Orange fenders that would fit unmodified in the 42mm forks would be the 37mm ones -- which have a maximum tire width of 27mm. So that'd be a nope. With modification (i.e., a dremel tool) you could get the Velo-Orange 45mm ones to fit in the 42mm foks, but those have a maximum tire width of 35mm, so still nope. Also with some judicious bending, cutting, hammering, duct-taping, and jubilee clipping, I think you could still get it to fit, but it may look janky to you.
Note that @Criggie has pointed out that the V-O requirement that the tire be -10 mm smaller than the fender may be conservative -- allowing for mud clearance which might not be an issue with the tires you want. But you won't know unless you put it all together.
If you're not into bodging fenders, then you would need to get the 37mm fenders and find wheels with a maximum width of 27mm (to be on the safe side). The safest thing is to wait until you have the bike in hand and can measure the actual fork distances and see if the 45mm fenders will fit -- but even then, your tires might not, so you still have to look for thinner tires -- or use different fenders.