Rick, there are several things that cause a dictionary / page index rebuild. The dictionary or page index is a in-memory cache of the available portal aliases and page names, which allows the provider to do a fast lookup of Urls when requested.
The principal ways the page index is rebuilt are:
1) application pool recycle, which drops the cached index and forces it to be rebuilt
2) available/required memory resources in the server cause asp.net to drop the item from the cache, which forces it to be rebuilt
3) a change is made to the site where a postback Url matches the regex value in the 'triggerDictionaryRebuild' regex attribute.
The actual message you will see in the logs will point to which one of these is the culprit, although it's pretty much impossible to tell the difference between 1 and 2 unless you can tie corroborating evidence (such as an app pool recycle message) into the timeframe. If it's (3) then you can manage this by reducing the matches down. It could be administrators making changes (adding, removing tabs, etc) that causes the issue, but I assume you'll know the answer to this straight away. The reason for getting two changes back to back are harder to discern - it could be a timing issue as two threads both find the page index empty and so both begin the process of rebuilding at the same time. That type of thing is hard to test for, and even harder to code for.
Now, the size of the page index is a function of the sum of the portal aliases x the sum of the pages. A portal with 2 aliases and 20 pages will equal 40 entries + 5 or so 'common' entries = so about 45. With the sorts of numbers of tabs, aliases and portals you're running, this is going to be a sizeable sized page index - the arithmetic is complex but you can probably assume something like 100,000 entries at a minimum. The friendly url provider also uses standard DNN stored procedures to retrieve the information, so you're looking at running the 'GetTabs' stored procedure.
You might want to narrow down where the cpu usage is originating from ; if it's the database process, then there *may* be scope for optimising the query (some of the standard DNN queries are not at all optimised for performance). If it's the looping process of reading through the large size of the result set, then there isn't much you can do about it short of rewriting that part of the code. The module is built around the assumption that a Url either exists in the index, or it doesn't exist and should return a 404. That's why there is so much code devoted to keeping the index current.
If you have a test server you can look at using the Url Master 2.0 version to see if you see any improvement. This has a crucial difference in the way the page index is rebuilt. For a start, you can specify a 'chosen portal alias' (though I suspect you may wish to use multiple aliases) which immediately reduces the size of the index to roughly equal to the number of tabs (because each tab effectively only has one valid portal alias). The second improvement is that the page index is built incrementally, one portal at a time. So, if you have 200 portals, and only 10 of them get any serious use, then as each request comes in for each additional portal, the page index will be incrementally increased, rather than being built all in one big go. Obviously the big difference is the cost between the free module and not, so that's a choice that you can make. There isn't any chance of the Url Master 2.0 changes being backported into the Friendly Url Provider because the codebase has been irretrievably forked such is the nature of the fundamental changes in the new version.