Вы хотите Lists#cartesianProduct(List<List>)
:
final List<List<String>> product =
Lists.cartesianProduct(ImmutableList.copyOf(map.values()));
System.out.println(product);
// prints: [[anyType1, first1, second1], [anyType1, first1, second2], [anyType1, first1, second3], [anyType1, first2, second1], [anyType1, first2, second2], [anyType1, first2, second3], [anyType1, first3, second1], [anyType1, first3, second2], [anyType1, first3, second3], [anyType2, first1, second1], [anyType2, first1, second2], [anyType2, first1, second3], [anyType2, first2, second1], [anyType2, first2, second2], [anyType2, first2, second3], [anyType2, first3, second1], [anyType2, first3, second2], [anyType2, first3, second3], [anyType3, first1, second1], [anyType3, first1, second2], [anyType3, first1, second3], [anyType3, first2, second1], [anyType3, first2, second2], [anyType3, first2, second3], [anyType3, first3, second1], [anyType3, first3, second2], [anyType3, first3, second3]]