Impact of the size of hosts.deny on network responsiveness

It will make the initial connection a fraction slower, but past that should have no bearing on the responsiveness once connected.

Generally speaking hosts.deny is pretty fast: on a test I just ran, a zero-length hosts.deny took 0.93 seconds to initiate and close an ssh connection ("time ssh testhost env"). With a 64,010-line hosts.deny (of the form "ALL: 10.10.x.y", with x and y running from 2 to 254), the same connection took 1.03 seconds. All times were averaged over four samples.

Obviously your mileage may vary, and so I suggest you test, but I doubt you'll have serious problems.

It is also possible to use iptables with connection tracking, which I think would be slightly faster and have the added benefit of being protocol agnostic, i.e being equally suited for denying connections to tcp/udp/icmp or whatever service you may be running.