Rendering nodes and other content compatible with all themes With a group of several people we're creating a system for students.

Now, on that system we're going to have all kinds of modules that have output, e.g., content types with information about events, a page with a hierarchy of people and groups.

What is the Drupal way of rendering this output?  

I know that rendering should be done by the themes. But the problem is that our users should be able to pick a theme they want. Creating separate output for each of those themes is just unfeasibly hard.
I know that rendering should be done by the themes.


That is not exactly correct. Theme functions are generally defined from modules, and themes can override them, or implement a theme function that is specific for a purpose. 


theme_node_preview() is implemented by the Node module
theme_field() is implemented by the Field module
theme_rdf_metadata() is implemented by the RDF module
Other theme implementations are contained in the theme.inc file


If you are creating the output for a page, the code for generating it should be in a module. That is because it's a module that can implement hook_menu(), which is the hook that defines the menu callback used for pages.
That is what is done from Drupal core code with node_view(), which is the page callback for node/%node, and node/%node/view. The page callback is defined from the Node module, not from a theme; themes can eventually alter the output of node_view() through the node.tpl.php template file used from node_view() to render the node page.

As for outputting the result, there are two methods: 


Returning a string containing the HTML output
Returning an array with a specific structure (it is called render array) that can be used from drupal_render()


As example of a page callback that returns a string, see aggregator_view(); as example of page callback that returns a render array, see node_view().