hum...

Le problème ne vient pas de malloc mais plutôt de sizeof.
En effet, sizeof sait mesurer la taille des données brutes qu'on lui donne en paramètre, toutefois il ne peut pas présupposer de la taille d'un déréférencement de pointeur. Pour lui un pointeur pointe au moins sur un bloc de mémoire de la taille du mot de base du compilateur (ex. 8 pour un processeur 64 bits).

L'exemple simple ci-dessous pourra éventuellement t'éclairer.

#include <stdio.h>
int main() {
 char* c = NULL;
 printf("sizeof(c) = %lu\n", sizeof(c));
 printf("sizeof(char) = %lu\n", sizeof(char));
 return 0;
}

Ainsi, l'exemple que tu donnes par de toute façon dans la mauvaise direction quant à ton utilisation de sizeof.
Je te conseille plutôt un écriture du style pour t'en sortir.

struct case_t
{
 Casetype type;
 Quantite qte;
 int pheroNid;
};
typedef struct case_t *Case;

Afin de corriger ta ligne

map[i][j] = malloc (sizeof(Case));

en

map[i][j] = malloc (sizeof(struct case_t));

car manifestement, celle-ci est fausse et ci cela fonctionne sans segfault chez toi, c'est plutôt étrange...

Un conseil pour finir, évite les typedef de pointeur, c'est un truc à s'embrouiller le cerveau pour pas grand chose.