I've produced a style where I curently have a custom options page where I allow the user set text for footer, twitter user plus some other activities which is effective. Now let me add the functionality of letting the consumer that installed the theme choose which font that needs to be employed for content on the website. How do i make this happen? I'm able to most likely produce a php file that results something similar to:

<style type="text/css">
body{
    font-family: <?php echo get_option('my-font');?>;
}
</style>

and can include that file in header.php, but this means that I must hit php for each request this css and I wish to avoid when posssible.

Really, I'd recommend placing that code directly inside your header.php file. You'll be parsing PHP code, so there is no reason you cannot parse that get_option() request simultaneously. I have used an identical system to develop a random header image on each page load according to WordPress options before too.

For just one theme I built, there have been CSS options aplenty, and so i made the decision to create static CSS files once the user made changes. To obtain around caching, I'd keep timestamp from the last update, and echo it like a parameter within the CSS URL

<link rel="stylesheet" type="text/css" href="/path/to/generated/css.css?ver=<?php form_option('theme_name_css_timestamp'); ?>" />