Hide link formatting Firefox extension
Always prefer const when declaring variables - only use let when you have to reassign a variable. const requires less cognitive overhead, when you know at a glance that something's never going to be reassigned.
Style toggling You're currently toggling the style with styleSheet.insertRule(rule, 0) and styleSheet.deleteRule(0). I think it would be a little bit better to take a different approach.

Who knows what insertRule(rule, 0) and deleteRule(0) do at a glance? Probably not a whole lot of people; it's not a very common API that's used.
What if you need to expand the extension to add additional rules? Then using multiple rule indicies could become repetitive.

One alternative would be to, on toggle, either append or remove the style tag from the &lt;head&gt;. Another alternative would be to assign or clear its textContent. See below for example.
hideLinks is not an altogether precise name. At first glance, someone seeing a variable named hideLinks would probably think it sounds like a function that, when called, hides links. Maybe call it something else, like linksAreHidden. You can also make its toggling more DRY:
if (hideLinks) {
    styleSheet.deleteRule(0);
    hideLinks = !hideLinks;
} else {
    styleSheet.insertRule(hideLinksRule, 0);
    hideLinks = !hideLinks;
}

can be
if (hideLinks) {
    styleSheet.deleteRule(0);
} else {
    styleSheet.insertRule(hideLinksRule, 0);
}
hideLinks = !hideLinks;

Or, even better, rather than having a persistent outside variable, you could simply check to see whether the style element is attached or has content. See below for example. This is what I'd prefer - let the style node (which must exist regardless) be the source of truth, rather than introducing another variable that needs to stay in sync.
Request object You currently have
if (request.isQuery) {
    return Promise.resolve({
        hideLinks
    });
}
// otherwise, insert or remove style rule

I think it'd be better to be more explicit. What if you add a 3rd request command, or a 4th request command? Instead of having an implicit &quot;Else, if this isn't a query, then do THIS instead&quot;, I'd prefer to always send a property indicating what the command should be.
Perhaps like this, using a isToggle property:
const hideLinksStyleText = `
a,
a:hover,
a:focus,
a:active,
a:visited {
text-decoration: none !important;
color: inherit !important;
background-color: inherit !important;
border-bottom: initial !important;
}`;
const styleTag = document.head.appendChild(document.createElement('style'));

function handleRequest(request) {
    const linksOriginallyHidden = Boolean(styleTag.textContent);
    // Do not modify if request is only a query
    if (request.isQuery) {
        return Promise.resolve({
            linksAreHidden: linksOriginallyHidden
        });
    }
    if (request.isToggle) {
        styleTag.textContent = linksOriginallyHidden
            ? hideLinksStyleText
            : '';
        return Promise.resolve({
            linksAreHidden: !linksOriginallyHidden
        });
    }
}

The conditional operator can be used to make conditional expressions tersely. This:
const showLinksIconPath = {
    path: 'icons/link-icon.png'
};
const hideLinksIconPath = {
    path: 'icons/broken-link-icon.png'
};
function updateIcon(response) {
    if (response.hideLinks) {
        browser.browserAction.setIcon(hideLinksIconPath);
    } else {
        browser.browserAction.setIcon(showLinksIconPath);
    }
}

can turn into
function updateIcon(response) {
    browser.browserAction.setIcon({
        path: `icons/${response.hideLinks ? 'broken-' : ''}link-icon.png`
    });
}

Or, if you don't like the interpolation:
function updateIcon(response) {
    browser.browserAction.setIcon({
        path: response.hideLinks
            ? 'icons/broken-link-icon.png'
            : 'icons/link-icon.png'
    });
}

Tab checking You have:
if (!(tabs === undefined || tabs.length == 0)) {
  const activeTab = tabs[0];

The negations are slightly tougher to parse logically at a glance than they can be. Consider instead:
if (tabs &amp;&amp; tabs.length) {

In a larger project, you could use optional chaining and Babel:
if (tabs?.length) {

But optional chaining is only supported in very new versions of FF, and Babel isn't worth it just for this. (Babel is a good idea if you want to write a reasonably sized script and want to permit older browser versions to be able to understand the JS syntax you use. For a FF extension, it's less important, because almost all users will be on reasonably up-to-date browsers anyway - no need to transpile down to ES5 for those crummy IE11 users)