map uses usually uses only few MB for searching places and navigation

for good coverage i think celcom is good? bcos still have signal at those rural area...
for hotlink free basic internet i'm sure u will rage when u try to search a place using google map, and u need to top up RM30 every month to extend ur validity bcos there's no more 365 validity plan for hotlink... unless u use the RM30 credit to buy 1GB data every month then it's ok

if u r using android then just install HERE beta which is free and allow offline navi
however it often fail to obtain my location when i turn into offline mode...