Which of these three options for navigating govt services are better for the user?

I'm designing for government websites, specifically how the public finds government services. In some cases the user knows precisely what they want (eg copy of birth certificate) and in others generally (eg permits and licenses for starting a business which there might be many depending on your type of business).

We want users to use search, so our homepage has this prominently displayed near the top. We also believe that a 80/20 exists where a few services are the most popular, so we have popular services listed below the search.

Finally, we present categories as another way to find their service(s). We are considering three options (links to examples):

1) Vertical tab: users are presented with vertical tabs of categories on the left and associated services in the center. The homepage will lead to this page after presenting a few popular categories and then an "All Categories" link.
pros: users can quickly scan contents of categories and not lose navigation
cons: not very engaging or appealing, forces all users to leave homepage

2) Tiles: users are presented with category tiles on the homepage (we don't expect more than 12 categories). Clicking on a tile leads to a new page where services and subcategories are presented.
pros: users can see all categories from homepage; dedicated page of services
cons: switching between categories is not easy

3) Accordion (see link to example in the comments below): users are presented with category tiles on the homepage that expand to reveal most popular services and a button to see all services. Clicking on "All services" leads to a new page where services and subcategories are presented.
pros: You can reach the most popular items without reloading the page.
cons: You have to do two more clicks to find a service you need (assuming it's not popular, and not taking into account the back and forth clicks); When you open an accordion, it pushes down the tiles below. This might be a bad experience, because a user may need to scroll down to reach what was in the viewport before; collapsing it back would require an additional click

Which of these three options is better for the user and why?