I have two map types on my device - Tomtom and Navteq. The tomtom map is around 50% bigger in size.

Is this because it contains more and better information or that the compression algorithms in Navteq are better?

I'm comparing the latest files for both maps.

For my region the TA maps are 107MB and NQ are 75MB, but I find the NQ maps are better and have more roads included, so I don't think the size matters too much.

It could depend on the region which map is better. In the city or out the city can make a difference. Also (it's UK maps I think) it's possible there is a different detail for Wales, Scotland, .... so that one is better here and the other there.

I switched to NQ and tested a route back to my home (saved in favourites). It tried to take me into another housing estate which is a dead end and not linked to my house. I thought it might be because I had saved the favourite using the TA map so I deleted it and created it again. But it did the same thing. So I'm staying with TA even though I did find a wrongly labelled road.

That behavior can be caused by a wrong coding of a road. Example: NT map saying a raod is not hard paved, TT-TA code says it is. Or the other way around. Then your preference to use or not use non paved roads ... you get what I mean, I think.
Usually, bigger mapsize is more detail. However no map is perfect. And as I said before, for here it is TA the best and most complete, elsewhere it is NT, In Eastern Europe it's always the local providers that is preferred. I would not even be surprised when I would read that for one country (or more countries) members would have divided opinions. Depending on preferences, exact location (more city use or country use), ...
In fact. Yurbuh prefers NT maps, me TA and we are living in the same country. What needed to be proven ....