I intend to completely deny access to around 2000 IP addresses by adding proper entries in the hosts.deny file. Will this have an impact on the responsiveness of the system when accessed remotely by legitimate IPs?
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.
Can those 2000 addresses be aggregated down?
hosts.denywill take CIDR definitions. So it should, for instance, be quicker and easier to manage:
Than the equivalent:
10.0.0.1 10.0.0.2 10.0.1.1 10.0.1.2
Does it warrant a firewall?
If you're doing this a lot then it's really the duty of a firewall rather than the host itself. It would be easier to manage centrally and (as Jim notes) OpenBSD's PF with stateful tracking would make really light work of it.
[olafrv@eqqus ~]$ cat /etc/hosts.deny | grep ^ALL | wc -l 8004
With that amount I have no problems and no delays on a Intel Desktop Dual Core PC.
The file hosts.deny is auto mantained wiht denyhosts (http://denyhosts.sourceforge.net)