That's a big family tree Cathy

If you have to repeat the process in future you might get even better results by selecting a paper size of A1 or A0 - most PDF file 'printers' will let you go up to this kind of size.
By using A3 size the printing company is having to 'stretch' the PDF to fit the paper size they are actually using. Whilst PDF's generally stretch quite well, if you start with a PDF sized at A1 or A0 there is less stretching required to fit to the paper size. As you originally discovered, going from A4 to A0 (or larger if you ended up with 7 feet) produced a poor result, so although A3 was good, you may find A1 is even better

Edited to add:
If you are using Paul's technique with LibreOffice you may find that A3 is the largest 'A' size listed, but there should be a 'User' option which allows you to specify the exact size of the page which can be at least A1.