You are right about the importance of URI and HTML encoding. For this reason, it is a good idea to use the semicolon as the parameter separator instead of the ampersand. Using a semicolon means that URL attributes don't need HTML entity encoding. The problem characters will be caught by the URI encoding.
CGI.pm parses semicolons. It will use semicolons if the $USE_PARAM_SEMICOLONS is defined. Some homegrown CGI parsers might not handle them but people should avoid those in any case.
<A HREF="/my/cgi?gun=Smith+%26+Wesson;drink=Jack+Daniels">