Is the cat lying down, standing, sitting? If it's lying down then you are right that it may blend in to the sandstone and won't show off the cat as well as a base of a contrasting color. You could add some greenery or snow to seperate them visually.
If you're getting the base from McKenzie then just look through the catalog, at animals of the same color as your lynx, on the two different colored bases....should give you some clues.
