I ain’t no PHP wiz, but I got something to work that won’t duplicate the titles:
<?php
foreach( ( get_the_category() ) as $category ) {
$the_query = new WP_Query('category_name=' . $category->category_nicename . '&showposts=5');
while ($the_query->have_posts()) : $the_query->the_post();
?>
<li>
<a href="<?php the_permalink(); ?>" title="<?php the_title(); ?>"><?php the_title(); ?></a>
</li>
<?php endwhile; ?>
<?php
}
?>