Fatti:
A. A.a C._, nata nel 1968, politossicomane portatrice di infezione HIV (dal 1986), epatite B e C cronica, oltre che di una patologia tipo Borderline e di disturbi d'ansia, dopo avere beneficiato di prestazioni assistenziali, dal 1° aprile al 30 settembre 2001 ha lavorato come operaia generica presso D._ nell'ambito di un programma (temporaneo) di inserimento professionale-occupazionale effettuato tramite il Soccorso operaio svizzero (SOS) e retribuito dall'Ufficio cantonale del sostegno sociale e dell'inserimento (USSI). Durante questo periodo l'interessata è stata assicurata per la previdenza professionale presso la Fondazione X._. L'8 ottobre 2001 il dott. L._, specialista in medicina interna, ha certificato, con effetto da tale data, una incapacità lavorativa del 100% dovuta a malattia. In seguito l'interessata non ha più svolto alcuna attività lavorativa.
A.b Per decisioni del 15 aprile e del 13 maggio 2004, sostanzialmente confermate dalla pronuncia 15 novembre 2006, cresciuta incontestata in giudicato, del Tribunale delle assicurazioni del Cantone Ticino, l'Ufficio AI del Cantone Ticino ha riconosciuto all'assicurata una rendita intera dal 1° ottobre 2002 facendo risalire l'inizio dell'incapacità lavorativa (e del termine di attesa per il diritto alla rendita) al mese di ottobre 2001. C._ si è quindi rivolta alla Fondazione X._, la quale ha tuttavia negato, per difetto di competenza, un suo obbligo di prestazioni dal profilo della previdenza professionale.
A.c Mediante petizione del 13 settembre 2007, C._ ha convenuto dinanzi al Tribunale cantonale delle assicurazioni la Fondazione X._ e chiesto il riconoscimento di una rendita intera d'invalidità della previdenza professionale con effetto dal 1° ottobre 2002. Esperiti i propri accertamenti, la Corte cantonale ha accolto la petizione e ha condannato l'istituto di previdenza a versare all'interessata una rendita intera d'invalidità della previdenza professionale dal 1° ottobre 2002 (giudizio del 7 agosto 2008). I primi giudici hanno in particolare accertato che nessun mezzo di prova permetteva di dimostrare o ipotizzare con un grado di verosimiglianza sufficiente l'insorgenza, senza interruzioni di rilievo, di una riduzione rilevante della capacità lavorativa prima del mese di aprile 2001, rispettivamente prima dell'8 ottobre 2001, unica data sicura in cui una inabilità era stata espressamente attestata. Di conseguenza, avendo fatto risalire all'ottobre 2001 - vale a dire a un momento in cui l'interessata era ancora assicurata presso l'istituto di previdenza - l'incapacità lavorativa che ha poi portato all'invalidità, l'autorità giudiziaria cantonale ha ammesso la responsabilità della Fondazione X._.
Accogliendo il ricorso della fondazione collettiva, il Tribunale federale ha annullato con sentenza del 18 settembre 2009 (9C_684/2008) il giudizio cantonale e rinviato la causa all'istanza precedente per complemento istruttorio. Osservato come il medico curante (dott. L._) avesse per il 1998 sostenuto l'impossibilità di una ripresa lavorativa attestando così una inabilità completa e tenuto conto del comparabile complesso polipatologico (psichico e somatico) di fondo, la Corte federale ha rilevato la necessità di ulteriori accertamenti e ritenuto opportuno (maggiormente) approfondire se tra questa incapacità lavorativa, insorta prima dell'inizio del rapporto di previdenza, e la susseguente invalidità sussisteva un nesso materiale e temporale sufficiente (nel qual caso un obbligo di prestazione della Fondazione sarebbe stato escluso) oppure se questo nesso fosse in qualche modo stato interrotto (nella quale evenienza la responsabilità dell'istituto di previdenza si sarebbe giustificata).
B. Completato l'accertamento con l'esecuzione di una perizia pluridisciplinare a cura del Servizio accertamento medico (SAM), il Tribunale cantonale delle assicurazioni ha condannato la fondazione collettiva a versare a C._ una mezza rendita d'invalidità della previdenza professionale dal 1° luglio 2002 e una rendita intera dal 1° agosto 2002 (pronuncia del 13 aprile 2011). Da un lato i giudici cantonali hanno accertato che la fondazione non poteva essere chiamata a rispondere per le conseguenze derivanti dalle patologie psichiatriche poiché queste (in particolare il disturbo di personalità Borderline) avevano inciso in maniera rilevante (e continuata) sulla capacità lavorativa dell'assicurata già prima dell'entrata in servizio al D._. Dall'altro hanno però riconosciuto la competenza e la responsabilità di detta fondazione in relazione all'inabilità lavorativa di natura somatica, riconducibile all'infezione HIV, la quale aveva per la prima volta causato una incapacità lavorativa - poi anche (insieme alla componente psichiatrica) all'origine della successiva invalidità - nel mese di luglio 2001, quando l'interessata era assicurata presso la fondazione.
C. La Fondazione X._ si è nuovamente aggravata al Tribunale federale al quale chiede di annullare il giudizio cantonale e di respingere la petizione. Dei motivi si dirà, per quanto occorra, nei considerandi.
L'assicurata propone la reiezione del gravame e chiede di essere posta al beneficio dell'assistenza giudiziaria con gratuito patrocinio, mentre l'Ufficio federale delle assicurazioni sociali ha rinunciato a determinarsi.
Diritto:
1. Il ricorso in materia di diritto pubblico può essere presentato per violazione del diritto, così come stabilito dagli art. 95 e 96 LTF. Il Tribunale federale applica d'ufficio il diritto (art. 106 cpv. 1 LTF; cfr. tuttavia l'eccezione del cpv. 2) e non è pertanto vincolato né dagli argomenti sollevati nel ricorso né dai motivi addotti dall'autorità precedente. Nondimeno, in considerazione delle esigenze di motivazione di cui all'art. 42 cpv. 1 e 2 LTF, esso esamina di principio unicamente le censure sollevate; non è tenuto, come lo è invece un'autorità di prima istanza, ad esaminare tutte le questioni giuridiche possibili, se queste non gli vengono (più) riproposte (DTF 133 II 249 consid. 1.4.1 pag. 254, 545 consid. 2.2). Per il resto, il Tribunale federale fonda la sua sentenza sui fatti accertati dall'autorità inferiore (art. 105 cpv. 1 LTF) e vi si può scostare solo qualora questo accertamento sia avvenuto in modo manifestamente inesatto, ossia arbitrario (DTF 134 V 53 consid. 4.3 pag. 62), oppure in violazione del diritto ai sensi dell'art. 95 LTF (art. 105 cpv. 2 LTF). A prescindere dai casi in cui tale inesattezza sia lampante (DTF 133 IV 286 consid. 6.2. pag. 288 in fine), la parte che intende contestare i fatti accertati dall'autorità inferiore deve spiegare, in maniera circostanziata, per quale motivo ritiene che le condizioni di una delle citate eccezioni previste all'art. 105 cpv. 2 LTF sarebbero realizzate; in caso contrario non si può tener conto di uno stato di fatto diverso da quello posto a fondamento della decisione impugnata (cfr. DTF 133 II 249 consid. 1.4.3 pag. 254 con riferimento).
2. Nei considerandi dell'impugnata pronuncia, cui si rinvia, il Tribunale cantonale ha correttamente esposto le norme e i principi giurisprudenziali disciplinanti la materia, rammentando in particolare le regole che reggono il diritto alle prestazioni di invalidità della previdenza professionale obbligatoria (art. 23 LPP), la nascita di tale diritto (art. 26 LPP), la fine dell'assicurazione obbligatoria (art. 10 cpv. 3 LPP), la delimitazione della responsabilità degli istituti di previdenza nonché il coordinamento materiale tra primo e secondo pilastro (cfr. pure DTF 134 V 64 consid. 4.1.2 pag. 70; 133 V 67 consid. 4.3.2 pag. 69 con riferimenti), anche per quanto concerne la determinazione del momento a partire dal quale la capacità lavorativa dell'assicurato è da ritenersi deteriorata in maniera sensibile (DTF 123 V 269 consid. 2a pag. 271 con riferimenti). Alle considerazioni dell'istanza precedente può inoltre sostanzialmente essere fatto riferimento pure per quanto concerne l'esposizione delle norme regolamentari della Fondazione ricorrente relative al diritto a prestazioni di invalidità.
Giova nondimeno rammentare che, affinché un istituto di previdenza possa essere chiamato a fornire prestazioni, l'incapacità di lavoro deve essersi manifestata in un'epoca in cui l'assicurato era ad esso affiliato. Inoltre, tra detta incapacità e la susseguente invalidità deve sussistere uno stretto nesso materiale e temporale. A questo riguardo questa Corte ha precisato che vi è segnatamente connessione materiale se il danno alla salute all'origine dell'invalidità è essenzialmente lo stesso che si era già manifestato durante l'affiliazione al (precedente) istituto di previdenza e che ha causato un'incapacità di lavoro di una certa importanza (di almeno il 20%; DTF 123 V 262 consid. 1c pag. 264; cfr. inoltre sentenze del Tribunale federale delle assicurazioni B 127/04 del 21 aprile 2005 consid. 4.1, riassunta in RSAS 2005 pag. 549; B 96/01 del 10 luglio 2003 consid. 3.3, riassunta in RSAS 2004 pag. 449; B 36/01 consid. 1, riassunta in RSAS 2003 pag. 511, e B 100/00 del 16 febbraio 2001 consid. 2).
3. Nel giudizio impugnato, la Corte cantonale ha accertato, sulla scorta delle risultanze della perizia giudiziaria affidata al SAM, che sotto il profilo somatico, per quanto di rilievo, l'infezione HIV aveva mostrato una evoluzione progressiva con peggioramento clinico nel corso del 2001 e con conseguente (prima) insorgenza di una riduzione dell'abilità lavorativa del 50% dal mese di luglio 2001. Dal mese di maggio 2002 vi era poi stato un ulteriore peggioramento sia clinico sia immunologico della situazione che aveva reso necessaria una terapia antiretrovirale e comportato una completa e continua inabilità lavorativa. Per contro prima del luglio del 2001 dal punto di vista somatico la patologia non aveva mai causato alcuna incapacità lavorativa di rilievo. Dal punto di vista psichiatrico, il Tribunale cantonale, sempre facendo proprie le conclusioni peritali, ha invece constatato che il disturbo di personalità Borderline aveva influito sulla capacità lavorativa dell'assicurata nella misura (continua) del 20% dal 1986, pur non escludendo la possibilità di esacerbazioni nel periodo dal 1998 al 2001 che potevano aver determinato delle incapacità anche superiori. Essendo per il resto nell'agosto 2001 stato riscontrato un aumento dell'assunzione di oppiacei e di alcool oltre che un calo di rendimento nella seconda metà del periodo di attività presso il D._ - confermato dal suo stesso responsabile -, i primi giudici hanno ammesso una inabilità lavorativa del 50% dal luglio 2001 e del 70% dal dicembre 2001 con una notevole compromissione dello stato psichico a seguito del decesso del padre, cui l'interessata era molto legata, e del conseguente sviluppo di una sindrome depressiva cronica (ICD-10 F33.1).
Fatte queste premesse, la Corte cantonale ha stabilito che il tema del nesso materiale e temporale doveva in concreto essere esaminato distintamente in ordine alle due affezioni principali (infezione HIV, da un lato, e disturbo Borderline, dall'altro), poiché, pur non essendo escluse delle possibili interazioni, le due patologie erano qualitativamente separate e indipendenti l'una dall'altra. Ora, con rifermento alla patologia psichica, il Tribunale cantonale ha stabilito che fra l'incapacità lavorativa di almeno il 20% manifestatasi dal 1986 e la susseguente invalidità dal mese di luglio 2001 sussisteva una connessione sia materiale (le affezioni essendo sostanzialmente le medesime) sia temporale (nessuna interruzione [nel senso di un recupero durevole della piena capacità] essendo mai stata attestata), sicché la fondazione convenuta non poteva essere chiamata a rispondere di tale affezione che aveva influito sulla capacità di lavoro dell'opponente in misura rilevante già prima dell'affiliazione alla ricorrente. Diverso era per contro il discorso per la patologia somatica (infezione HIV) poiché, pur essendo già stata diagnosticata nel 1986, essa non aveva mai causato una incapacità lavorativa prima del mese di luglio 2001. Di conseguenza i giudici di prime cure hanno concluso che relativamente all'incapacità lavorativa riconducibile a tale patologia erano adempiuti i presupposti dell'art. 23 LPP per il riconoscimento (dal 1° luglio 2002) di una rendita del secondo pilastro da parte della fondazione collettiva presso la quale l'attrice era assicurata nel momento in cui (il 1° luglio 2001) l'infezione HIV aveva originato per la prima volta una incapacità lavorativa che ha poi causato un'invalidità.
Per la Corte cantonale, tale conclusione era inoltre confortata dalle altre risultanze agli atti, quali il fatto che l'assicurata si fosse, segnatamente dall'inizio del 1999 alla fine del 2000, regolarmente attivata alla ricerca di un posto di lavoro a tempo pieno e si fosse sempre dichiarata disposta e capace di lavorare in questa misura come pure la circostanza che all'epoca, prima dell'ottobre 2001, non era stata attestata una inabilità lavorativa.
4. Pur essendo quella della connessione materiale e temporale una questione di diritto e in quanto tale liberamente riesaminabile dal Tribunale federale, essa si apprezza comunque sulla base dei fatti accertati dall'autorità giudiziaria cantonale, e in particolare dei documenti medici. I quali fatti vincolano la Corte federale nella misura in cui non sono stati accertati in maniera manifestamente inesatta o incompleta (o comunque contraria al diritto). Spetta pertanto alla ricorrente che nella fattispecie intende contestare i fatti accertati dall'autorità inferiore spiegare, in maniera circostanziata, per quale motivo ritiene che le condizioni di una delle citate eccezioni previste all'art. 105 cpv. 2 LTF sarebbero realizzate (v. sopra, consid. 1).
Sennonché, la fondazione ricorrente, limitandosi a sollevare perlopiù censure di natura appellatoria, in quanto tali inammissibili in sede federale, difficilmente adempie a queste esigenze di motivazione in relazione ai fatti posti a fondamento del giudizio impugnato. Essa rileva - in maniera peraltro incompleta (v. sopra, Fatti Ac) - che nella sua decisione di rinvio del 18 settembre 2009 il Tribunale federale avrebbe imposto (unicamente) l'accertamento di una interruzione (del nesso materiale e temporale) e rimprovera all'istanza precedente di avere dapprima proceduto secondo il mandato, ma di avere poi proseguito in modo del tutto diverso e di avere deciso in modo completamente nuovo - attuando di fatto una revisione non dichiarata - come se le due malattie (Borderline e HIV) non fossero state preesistenti e fossero comparse solo durante il periodo di assicurazione. La censura, oltre che basarsi su premesse incomplete e imprecise, si scontra tuttavia con la realtà così come emerge dalle tavole processuali. Non corrisponde infatti assolutamente al vero che la Corte cantonale avrebbe trattato le due patologie principali come se non fossero state preesistenti bensì comparse solo durante il periodo di assicurazione. Basta leggere le dettagliate considerazioni del giudizio impugnato per rendersi conto che non è così. I giudici di prime cure non hanno mai messo in dubbio la preesistenza delle due patologie, risalenti al 1986, bensì hanno esaminato - conformandosi al senso della decisione di rinvio della Corte giudicante - nel dettaglio il loro sviluppo, la loro evoluzione e la loro incidenza sulla capacità lavorativa concludendo, sulla base delle risultanze peritali, che esse erano qualitativamente separate e indipendenti e che "soltanto" l'affezione psichica aveva inciso in maniera rilevante (e senza interruzione) precedentemente all'affiliazione alla fondazione ricorrente sulla capacità lavorativa dell'interessata, mentre quella somatica, seppur preesistente, aveva causato una inabilità lavorativa per la prima volta solo nel luglio 2001, quando l'opponente era assicurata presso l'insorgente.
Orbene, la fondazione ricorrente non tenta minimamente di spiegare in quale misura questo (decisivo) accertamento di fatto (cfr. pure DTF 132 V 393 consid. 3.2 pag. 398) sarebbe manifestamente inesatto, ovvero arbitrario, incompleto oppure contrario al diritto. A tal scopo non basta di certo rinviare vagamente alle dichiarazioni della perita dott.ssa E._ per sostenere che le due patologie facevano parte di un quadro complessivo determinante una incapacità lavorativa durevole del 20%. A parte il fatto che non spetta al Tribunale federale cercare nel voluminoso fascicolo i passaggi e le dichiarazioni (genericamente indicate) a sostegno della tesi ricorsuale, va ricordato all'insorgente - come già pertinentemente fattole notare dai primi giudici - che la dott.ssa E._, rispondendo a precisa domanda della Corte cantonale sulla possibilità che una mancata tenuta psichica incidesse sull'evoluzione delle malattie somatiche, dopo avere ricordato come questa eventualità non trovasse esplicito riferimento nei rapporti dei consulenti interpellati ai fini peritali e avesse piuttosto valenza di carattere generale, ha precisato in data 1° febbraio 2011 di non essere in grado di dire con quale certezza o verosimiglianza questo fosse avvenuto nel caso di specie. Anche per queste ragioni il richiamo operato dalla Fondazione X._, oltre che vago e impreciso, non sorregge pertanto la tesi ricorsuale.
In esito a tali considerazioni, la conclusione dei primi giudici di rendere competente e responsabile la fondazione ricorrente per le conseguenze invalidanti dell'incapacità lavorativa di natura somatica insorta (per la prima volta) durante il periodo di assicurazione non risulta né da un accertamento manifestamente inesatto o incompleto dei fatti né da una violazione del diritto federale (in generale sul tema cfr. pure la sentenza 9C_330/2008 del 4 settembre 2008 consid. 3 e 4, nonché le sentenze del Tribunale federale [delle assicurazioni] B 68/06 del 31 agosto 2007 consid. 6.5, B 73/05 del 3 maggio 2006 consid. 5.3, B 22/04 del 21 aprile 2005 consid. 2.3 e B 42/02 dell'11 febbraio 2003 consid. 2.2; v. inoltre Marc Hürzeler, in: LPP et LFLP, 2010, n. 22 segg. ad art. 23 LPP). Come sottolineato anche nella pronuncia impugnata, ad avvalorare questa conclusione vi sono le ulteriori risultanze agli atti, e in particolare il fatto che l'opponente si era annunciata alla disoccupazione in qualità di persona in cerca d'impiego a tempo pieno (sul significato attribuibile a tale circostanza cfr. DTF 134 V 20 consid. 3.2.1 pag. 22 seg.) e non era all'epoca, prima del mese di ottobre 2001 ed eccezion fatta per il periodo nel 1998, mai stata dichiarata inabile al lavoro, come inoltre pure la valutazione espressa dal responsabile del D._ circa la qualità del lavoro svolto dall'assicurata durante il periodo aprile - settembre 2001 che si concilia sostanzialmente con quanto riscontrato dai giudici cantonali, soprattutto per quanto riguarda il calo di rendimento accertato nella seconda metà del programma (sulla rilevanza di questi accertamenti cfr. Hürzeler, op. cit., n. 9 ad art. 23 LPP con i riferimenti alla giurisprudenza in materia).
Per il resto, la Corte cantonale ha diffusamente spiegato il motivo che l'ha indotta ad attribuire all'assicurata una mezza rendita d'invalidità della previdenza professionale dal 1° luglio 2002 - vale a dire al termine dell'anno di attesa di cui agli art. 29 cpv. 1 lett. b LAI e 26 LPP, nel loro tenore in vigore fino al 31 dicembre 2007 - e in seguito una rendita intera dal 1° agosto 2002. Essa ha ritenuto potersi validamente scostare dalle conclusioni dell'AI poiché, accertata una incapacità lavorativa dal 1° ottobre 2001, l'assicurazione per l'invalidità non aveva avuto motivo di indagare oltre l'esistenza di una inabilità di rilievo per il periodo precedente dal momento che questa sarebbe in ogni caso stata interrotta dall'attività svolta presso il D._ ai sensi dell'art. 29ter OAI. Ora, anche su questo punto la ricorrente - nel rilevare semplicemente che in caso di competenza la prestazione previdenziale andrebbe semmai versata per lo stesso grado e con la stessa decorrenza di quella dell'AI - non si confronta (sufficientemente) con la motivazione del Tribunale cantonale motivo per cui la censura non merita ulteriore disamina.
5. Ne segue che il ricorso dev'essere respinto e la pronuncia impugnata confermata. Le spese seguono la soccombenza e sono poste a carico della fondazione ricorrente (art. 66 cpv. 1 LTF), la quale rifonderà all'opponente, patrocinata da un legale, un'indennità per ripetibili della sede federale (art. 68 cpv. 1 e 2 LTF). In tali condizioni, la domanda di assistenza giudiziaria gratuita e di gratuito patrocinio dell'opponente è priva di oggetto.
Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 500.- sono poste a carico della ricorrente.
3. La ricorrente verserà all'opponente la somma di fr. 2800.- a titolo di ripetibili della sede federale.
4. Comunicazione alle parti, al Tribunale delle assicurazioni del Cantone Ticino e all'Ufficio federale delle assicurazioni sociali.